iPhone iOS 7 iMessage cache

I recently upgraded to an iPhone 5s (obviously running iOS 7) but downgraded on the storage (32gb -> 16gb). The reason for this was, that was what the store had available and I was right on the border of needing 32gb vs 16gb anyway. With everything reinstalled and deleting some larger games like Infinity Blade 1 and 2, I have 2.6gb of availabe storage on the phone.

To see if I could free up any additional space, I looked at the Usage tab in Settings and saw that iMessage is taking up a whopping 508MB of space. I tried deleting messages in iMessages, didnt work. I have a clear inbox and it still takes up 508mb of space. I have a work issued iPhone 5 which shows 3.6mb used for iMessage.

How can I reset this? I read somewhere that it may be storing older messages or media but I haven't seen any posts on how to correct the issue. With only 12-13gb of usable storage, having half a gig taken up for (supposedly) deleted messages really cuts in to it.

Anyone able to help with this or provide me with information on how to clear the iMessage cache? Ideally I'd like to do so without wiping and setting up as a new phone.

Thanks!

I just noticed another thread on this as mentioned. I'm going to start following that; no reason to have 2 threads covering the same thing. I wish there was a simpler way to correct this aside from hacking in to your own back ups and deleting messages.

to answer the other post, yes, I cleaned out my message app and rebooted both by using the power button then again doing a hard reset. Still shows up 508mb.

Thankfully my problem isnt as bad as 1.9 gb or as some people in the other threat stated they had over 5gb of space wasted. Guess we'll just have to wait and see if there is an easier solution that appeaers.