Messages arent stored on your sd card they are stored in your ROM wich is where your apps are stored. Go into setting>sd card & phone storage> then look at internal phone storage. IF that is really low like 5-20 mb try unistalling some apps such as google earth raging thunder 2 and other bigs one if you have them. You will then have enogh space for messages. If your rooted go in the market and download cache mate it will clear the cache of your apps. If not just go in a clear caches manualy
There are various apps that will back up your messages as well. Before I switched to GV I used (I believe) SMS backup...it saved messages to Gmail. Just text though, not MMS. Look around though, it never hurts to b/u them up somewhere...
You don't have to be rooted to clear the individual caches of assorted apps. "Quick App Clean Cache" will do the job; paid app -- just under a buck. VERY eye-opening to see how much space some apps are truly using on a daily basis. I've been using it for several weeks and find it to be stable and smooth, operationally. Also super simple/intuitive to use.
Note: this app is essentially a front end, taking you quickly to the native settings area per app. In other words, that clear-cache function is built into the Droid, but it's a pain getting to it, per app, without this handy 3rd party app. No relation to developer. I just love his/her handiwork.