I believe I figured out a "work-around" solution without having to restore your entire phone.
1. Connect your phone to Sync it to Itunes
2. Within Itunes click on your phone on the left side and within the right nav menu click on "Info" tab
3. Within the Advanced Section click on Contacts
Hit "Sync"
What this will do is allow iTunes to replace your contacts on your iPhone with the contacts on your computer / laptop.
This worked for me, I was able to successfully send text messages without it coming back and saying the number doesn't exist.
Make sure your contacts on your computer is up to date. I have a MacBook Pro so the contacts were easy to update on my laptop.
Not sure about windows, sorry.
I hope this solution works for you all.