I had the same issue when switching to a Nexus 5.
https://appleid.apple.com Try going here and removing the phone number from the "Phone Numbers" section. I still have friends who try to message me and their iOS assumes I'm using iMessage. The "retry as SMS" feature is the only method that works.