There is something else you can try (my mail has been working fine, so I don't know if this will help).
Mail has a built-in feature under the Mailbox menu called "Rebuild Mailbox". If you have more than one email account, click the disclosure triangle on your Inbox and single-click onto any mailbox. Goto the Mailbox--> Rebuild Mailbox and rebuild each of your mailboxes.
If you have saved items, they are also separate mailboxes and the rebuild works on those as well.
You may want to give this a try. With over 7 million OS X users, you can bet there are millions of people using mail without problem. A few months back I switched from Entourage to mail/address/ical/isync for the integrated features. I found it is actually LESS keystroke to do the same function in mail as in Entourage...and mail's junk mail filter is superior to manually writing rules in Entourage.
So, in conjuntion with trashing the preferences, definately try using the Rebuild Mailbox function. Good luck!
