Just had to fix this for someone recently. Backup your mail first, then do the following:
Quit Mail.
Open ~/Library/Mail/V2/MailData/ (you can simply hit Cmd-Shift-G in the Finder and copy/paste that in the box that appears).
Find the file(s) that start with Envelope Index (there were three on my system, but it will vary). Toss them in the Trash.
Reopen Mail.
It will take a while to recreate your mailboxes and reimport the messages, and then you shouldn't see that problem again.