Hi Everyone, just looking at the original post. I've had something similar recently. I moved from Nokia to iPhone 5. Since I travelled overseas sometimes I fell in the habit with my nokia to enter all phone numbers with the respective IDD (international country code) included. So in Australia for example I would enter a cell phone number, say, 0412 345 678 as +61 (0) 412 345 678. Now the Nokia system coped with this and if I called when out of country it would just work. I didn't first have to try and figure out what that country's dial out code was (and most countries are different)
But Apple can't cope with that way of entering cell phone numbers which was the reason I could not text to any of my contacts. I could make / receive calls and receive SMS's. (there's a setting in iphone which tells it which country the phone comes from and it's a smart phone so figures out correct dial out codes itself)
To solve I had to manually change all my numbers. Appel were quick to replace my phone and off course upon entering a cell phone number manually (and without IDD code) the text was succesful so it looked solved. However after all my contacts came back from iCloud the problem returned. Eventually a technician at my telco figured it out. Hoorah!!
So anyone who has this issue should also check how they have entered their numbers. This is much easier than the numerous trips to telco / apple, many resets, network settings checks and checking the ##5 etc checks.
Hope this helps someone, it drove me crazy for a couple of weeks.