You might want to first try:
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.