Same here. Incredibly frustrating.

Did you unregister your device(s)? After doing this I think people's iPhones know your number isn't an iPhone anymore and after it fails to send the iMessage it sends it as a regular message. The below link helped me:

http://support.vodafone.com.au/articles/FAQ/How-to-deactivat...

I'm still having occasional problems with not getting texts but for the most part it's fixed.