i have looked everywhere for the solution to this. i thought i had found the solution (see below), but i do not have a "mail" folder in my library...help! 
Here are the exact steps they had me follow to get to that location:
1. Click Finder in the dock
2. Press and hold the Option Key
3. Select Go-->Library from the menu bar (still holding down the Option Key)
4. Double Click the Mail Folder
5. Double Click the V2 Folder
6. Double Click the MailData Folder
You should see the "Envelope Index" files there.
3. Move all "Envelope Index" files to the desktop - for me there were of them.
4. Restart Mail - I received a message that mail had to import files, I hit continue and when it was done (took about 5 minutes to process all 6 accounts I have) everything was back to working right.