I had the same problem, but I seem to have fixed it after some trial, error, and hair loss. Here's what I did:
1) Backed up all my data (SMS, MMS, Contacts) in various ways.
1a)Backed up my contacts using the Import/Export feature in the Contacts app.
1b)Backed up my SMS and MMS using 'MyBackup' on the Market. There is a free version for 30 days, which works. In the app, just select Backup -> Data -> Local (SD Card) -> Then select all the data you want to back up.
2) Factory reset
3) Set all my settings in the messaging app, and made sure they stuck (Closed the app, reset the phone, etc.)
4) Reinstalled 'MyBackup' from the Market, and restored my data for it's backup, and imported all my contacts again.
This may not be the quickest or most continent way to fix it, but it seems to work!