My sister-in-law has been dealing with the exact same problem since before iOS 7 was released, but I finally got the issue resolved today.
First, she was still on iOS 6. So I backed up her iPhone using iTunes on my computer. Then I completely erased the phone (Settings > General > Reset > Erase All Content and Settings). When the phone booted back up, I told it NOT to restore from a backup and instead, set it up like a new phone. Once I had an operating iPhone without any data on it, I was able to upgrade to iOS 7 (Settings > General > Software Update). When that completed, I used iTunes to restore her backup, but the iPhone was still out of space.
She had deleted all conversations in the MESSAGES app (so it was completely empty), but "Settings > General > Usage" still showed that MESSAGES was taking up 11.2 GB of space. So I downloaded and installed "iBackupBot for iTunes". This program can open the backup made in iTunes so you can view what is there and if needed, modify the backup files. So I searched the backup and under "Other Multimedia files", I sorted by filename and found a bunch of large files in the following location:
MediaDomain/Library/SMS/Attachments/
When I selected all of the files in that location, it showed I had 3075 files selected for a total of 11.2 GB. That was exactly how much space her iPhone was reporting as being used by the MESSAGES app. So I deleted all 3075 of them (as I said, she had already deleted all of the message conversations on the phone, so those 3075 shouldn't have been there). Once these files were removed from the backup, I again restored her phone using this backup (which was 11.2 GB smaller than before).
I'm happy to report that her iPhone is working perfectly again, she can backup to iCloud again, and she has over 11 GB free now!!!