So all your message are gone out of the messaging app but in settings 5.6 gb is still being used?
Several things I'd try first are the basics. Sync with iTunes. Reset the phone (home + power until you see the Apple logo).
You can try restoring from a back up too however that didn't work for me which leads me to this.
Sometime in iOS 6 there was a bug that when you deleted your messages they would disappear but the content would remain on the device. It was fixed but if you were effected the problem was never resolved for those affected.
In iOS 6 it went unnoticed because in settings you could not see message data like you can in iOS 7.
I found two sure fire fixes. Download ibackupbot on you computer and manually edit your back up and remove them all and restore from that back up.
Or restore as new and start over.
Like mentioned search this forum and you'll find threads on the subject particularly the iOS 7 section.
Good luck.
