A third party app may help, but what I've found to be the case with this issue is old MMS and SMS messages taking up too much memory. You could just delete the old ones until it works, but I deleted them all. If you don't want to pick and choose, and it's probably the biggest messages you want to keep, that's just always the way, most third party apps will offer you some kind of backup or save option for your messages. I think Astro File Manager's backup will save MMS/SMS, and any backup app that's worth anything will offer messaging saves. Also, clear your FB cache, really any and all caches, but FB seems to be the main cause of memory loss affecting phone performance (this is reason #121 why FaceBook should be banned and removed from all devices). Mainly though clearing out your message history should help, then the cache thing if you're still having issues. Also if you're rooted disabling the stock app helps.
