Using a third-party messaging app, try sending it with a stock one (ie. Messages or Hangouts)
Not using a third-party app, try making a call to the number. If you get a pop-up message of any kind relating to "Call fail, disconnected, etc.." - you have a network connection issue. Pull out the battery and restart your phone.
If neither are the case, try to send a text message to their full [11 digit] number.
I would attempt both number input ways: spaced & ran together (ie. 12345678900 & 1 234 567 8900)
Removing any symbols, signatures, sound(s), pictures, wallpapers, or ringtones from the message can greatly increase your chances of successfully sending it
Try using your device's Common Procedures and check that the Short Message Service Center (SMSC) number is programmed correctly.
HELPFUL TIP: Reprogram the SMSC number, send a text to that number again, and see if the issue is resolved
If all the above fails, contact customer service and see if they can figure it out.