This is what fixed it for me.
If you're using a messaging service, which you have to now for A2P, then the FROM variable in the REST call should be the Messaging SID, not a phone number...
This solution is burried in the documentation and not mentioned anywhere in tutorials...