After exhausting all suggestions from Apple, including being given a case number and being told that someone would contact me, I called AT&T. The AT&T tech was very helpful and expressed exasperation that Apple techs did not give me the correct method to restore the one contact in my iPhone that I could not text. The tech from AT&T said that Apple knows how to fix the problem, and doesn't know why they put me through at least 4 grueling hours of "fixes". So now I'm wondering what is Apple's problem that they are not telling us how to fix this, but instead they let us languish on this page asking eachother for help! Ridiculous!
Here's what worked for me: 1.) Write down all the contact's information before deleting anything. 2.) Delete all iMessages from that particular contact. 3.) Delete not only messages just to that contact, but also all group messages including that contact. 4.) Delete that contact from your iPhone contacts list. When you're sure you've deleted all traces of that contact in your iPhone then do number 5.) Re-enter into the contact list just the contact's phone number but do not enter the last digit of that number. Instead substitute x for the last digit. 6.) After that is done to to your iMessages and type in the contact's number ending in the letter x and send a test message. If the message is still undelivered then delete that text and the number in your contact list and go through steps 1-4 but when you get to step 5 re-enter the contact's phone number substituting the number 0 for the last digit. Then send another test text.
This is what fixed the problem for me. Now if Apple would fix the bug once and for all we all won't have to go through all these steps to make the darn iPhones work! Apple owes us some credit on our next iPhone purchase, that is if anyone is still an iPhone fan. I'm thinking there'll be a lot of disgruntled iPhone users switching to Samsung!