Do you have a custom ROM with journaling turned off? If so your data has become corrupted. If you made a backup in Clockwork, now is the time to restore.
Settings--Applications--Manage Applications-- All-- Messaging-- Clear Data
If you are running a custom recovery, try fixing the permissions under advanced (or if you have ROM Manager, you may be able to do it from the app). Then reboot and see if that works.