Huh, that's weird. What I'd do is use an app like SMS Backup/Restore to backup all your messages, clear data from Messages app by going to Settings>Applications>All>Messages and then clear data, and then test it out. If messages are back to normal, than restore your messages with the app.