Fixed:
After doing the restore and it not working I decided to give up on this. But when I went to use Siri to send a text message to someone I text daily it all of a sudden said that the contact doesn't have a phone number or email which they do (I double checked).
I made sure all my contact databases were off (iCloud, Yahoo, other Gmail accounts) except the one I use (main Gmail account). iCloud was on. I guess the restore turns it back on automatically. It was empty anyway so I turned it off. Didn't fix it.
I then turned off my contacts for my main Gmail account and deleted all contacts off my phone. I then turned it back on and waited a while for contacts app to repopulate with all my contacts.
Didn't fix it.
I then took a screen shot of the contact and deleted the contact from Gmail and remade it.
That fixed not being able to text that person AND it also fixed the issue with me being able to ask for my last unread message from anyone. STRANGE.