The LED solution is very neat, nice work on the thinking outside the box but this is not practical for what I want since there are restrictions on range, interferance and you have to point the handset at the arduino. Horses for courses though, it may work fine for what you have in mind.
If you have a HTC android you can root it and use the connector on the phone like a TTY serial port:
Again this is very cool, but has its restrictions, i.e. voids the warranty, only applicable to certain phones, etc.
The next option is bluetooth. This is where I'm making some investigations. there are a few options that I've found so far:
(i) Get a Bluetooth enabled Arduino board:
The board is a little pricey, but then again bluetooth chips do not appear to be that cheap.
(ii) Use the sparkfun adapter on a regular arduino:
(iii) Get an RS232 to Bluetooth adapter:
Do all android phones support bluetooth? I don't know.
The next option is WiFi:
There is a wifi shield, again a little pricey, but worth looking into.
At the moment I'm considering getting the bluetooth Arduino board but would love a solution in the region of £20.
I would be interested to hear your thoughts on this as I want to do something very similiar.