This. Apparently there was a bug between 6.0 an 6.1 that caused attachments to not get deleted when conversations were. It hit me too, I had 900MB left over down from 3GB after clearing all my convo history. If you want to clear all this out without losing any other data, back up your phone to iTunes and use something like iBackupBot or similar to delete everything in HomeDomain/Library/SMS and MediaDomain/Library/SMS in your backup and then erase and restore your phone with this edited backup (make sure you make a copy of the backup before you do this in case something fails with the backup editor).
You are absolutely genius - I followed your instruction and freed up 650MB of dead space on my iPad mini with iOS 7 !
Thank you so much for the info. Apple should pick up this issue and resolve it ASAP. I just can't see any excuse for not fixing this bug.