Comment Easy Fix (Score 1) 415
I understand why this is difficult, but have found a repeatable (easy-ish) fix.
On the iPhone (and this sucks, because it's for the people trying to send you a SMS [not you on your new Android device]):
1) Turn off iMessage (from the Settings)
2) Go and send a SMS to the phone number of the Android device.
3) Turn back on iMessage
-Note: If this doesn't work, before #1; delete the number from the contact and add it back after #1.
