Yup --- had the same problem.
Quit Mail.
Go to your ~/username/Library/Mail folder.
Look at the date on your LSMMap and/or LSMMap2 files. It should be "Today". If it is not, I'll bet you it is the day that you started having the trouble with Mail.
Rename the LSMMap and/or LSMMap2 files.
Launch Mail and it will recreate the files.
You'll probably have to retrain you Junk mail. Mine retrained really quickly and has been working better than before.
What really saved me was that I had SilverKeeper (
http://www.macupdate.com/info.php/id/7646 ) running backing up my user files to a sparate directory -- so I just grabbed a copy of the files from BEFORE the corruption occured, I'm sure that helped me.