I didn't realize that Messages was now the default SMS/MMS app for Android.
Anyway, you could try the following:
Keep in mind that a full phone reset will completely all of the data stored on your phone. Messages, pics, etc. And there's not guarantee it will fix the problem.
The app I'm using now is Android messanger, as far as I know it was the replacement/re-branding of google messages. I don't think messages is available on the app store anymore, but I could be mistaken
At one point, that app was just called Messenger. The current name for it is Android Messages. It is still avaialbe.
@pmikeyreid, if you are really desperate and want to give factory reset a try, you can use adb backup and restore to save your user apps and data on a computer for restoration after a factory reset. The instructions were written in a galaxy nexus thread on xda but it works the same for any android device.