There is an option in settings->messages for iPhone users that enables sending iMessages as text if iMessage isnt avaiable. It is turned off by default so it needs to be turned back on (it used be on by default but one of the ios updates must've changed it). Had the same problem recently after my sister switched from iphone to a samsung galaxy. Simple solution
There is actually a better option to fix this, I had a iPhone 5S and swapped back to my Nexus 5 and used this to fix my issue. Go to (supportprofile.apple.com) login with your Apple ID, it should have listed all your iOS devices that have been activated on that Apple ID. Just delete the phone that you ditched and you are good to go.