Kmmastel, I know that failed texts are the last thing you expect from a new phone. Lets take a look into what could be happening. Which app are you using to text? Verizon message + or the default app?
Follow us on Twitter @VZWSupport
If my response answered your question please click the 'Correct Answer' button under my response. This ensures others can benefit from our conversation. Thanks in advance for your help with this!
Had this same error message with my new S7 Edge when trying to send MMS messages. SMS texts worked fine, but not MMS (pictures, group texts, etc.). I found another post that identifies the "Get a new SIM card" solution as the "correct answer", and that thread is locked now so I cannot reply with the real answer. I would love to reply to it since that is NOT the correct answer especially if you have recently switched phones and/or had issues with Activation.
Go to the phone status page. (on my S7 Edge, that page can be found under Settings, then scroll down near the bottom to "About Phone", then click on "Status". With other phones you may have to look around for a while to get to this page.)
Scroll down until you see "My Phone Number" and see if it is all zeros. (Don't be confused by the bullet point called "MIN", which should also (in most cases) display your phone number.) If "My phone number" is all zeros, this is the problem and you must call Verizon and tell them to manually re-activate you phone with the correct phone number in this field.
The explanation is that Verizon identifies your phone internally using the MIN setting... apparently this stands for "My INTERNAL Number", and that is why you are able to make and receive calls and texts. Verizon knows who you are. But when you send a MMS record, the phone is transmitting the "My Phone Number" information instead to the recipient, and all zeros is not a valid number. So the message is misleading... despite what it sounds like, it is not the Recipient's address that is invalid, it is YOURS, and the MMS is rejected.
If the Verizon tech balks at this explanation, ask to be forwarded to a Level 2 tech. They have access to information that the Level 1 techs do not, and this problem and its fix is documented and confirmed.
Good luck everyone!