Have you tried installing a different messaging app and see if it yields the same results?
As a temporary solution try downloading Android Messenger from Google and switch the default messenger to it. Try sending a message and see if you continue to get that message sending error. If you do, obviously some additional sms/mms settings need looked into.