All-

I have found a solution to this problem, at least for me. My issue was after linking my phone to Facebook, the Facebook app added the country code to each phone number. If you retype the phone number in a new section of the contact, you can get the message to sent and then it will always work after that.