I found a post with this solution that worked for me - .Do a backup, then download ibackupbot. It lets you look into the contents of that backup. Look in system files>mediadomain>library>sms>attachments. I found a ton of huge files related to long deleted texts. ibackupbot let me delete all that old crap. I then restored the phone with that now modifec backup and Bingo! freed up 9 GB. No problems.
But note, if you are not technically inclined you probaly don't want to be digging around and deleting back up files. You delete the wrong thing and you could jack up your phone badly. Be careful.
I had this problem as well as my "other" useage being extremely high. If you have deleted all of your messages, another alternative is to plug your phone into iTunes on a computer and do factory reset. Backup your phone first, and then go in and do the reset. Your contacts and apps and everything will stay as well as any notes or anything you have. I think the only thing I had to redo was my calendar and my alarms, which was a small price to pay for the added memory