Does it have to be Bluetooth and does it have to be an Android phone ?
If you have a web connected Arduino, such as the Arduino Ethernet or an Arduino Uno with Ethernet shield you can send a message to ANY registered iPhone.
This is very simple to do and using PHP and Prowl (
http://www.prowlapp.com/). Using this you can send different messages to an iPhone depending on what input comes into the Arduino. ie different push notifications for different switch inputs.
I have this in my home, so when my house alarm goes off, I get a instant push notification on my iPhone.
If it is to prove a concept of operation, this would be an easy method.
Another would be to use an email gateway to send a text to your mobile. This depends on what carriers are being used etc though.