We get this all the time with our network home directories (not applicable to your situation, I'm sure). The fix (for us, anyway), is this:
Quit Mail. Open your Library folder, and open the Mail folder in there. Look for any files whose names start with "Envelope Index" and trash them.
Launch Mail. It'll say that it needs to import your mail. This is okay. It'll go through your mailboxes and reindex your mail.
Hope this helps!