Try going to settings-->Application Manager-->Messaging and clear the cache and clear the data.
If that doesn't work, try downloading a cache cleaner utility or a general utility app like ZD Box and use that to clean your cache.
If that still doesn't clear it up, spend some time in application manager moving as many applications as possible to your SD card.
Repeat the same process with a file manager application. Move all photos, music, and videos that might be on your device over to your SD card.
And please consider joining our community. Welcome to AF!