Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
I too have had the exact same problem with a new iMac running Snow Leopard. My previous Mac is still set up and is running Mail without any problems so I assume everythign is OK at the server end.

I have deleted ALL email from the server by going to the Advanced tab for each email account and clicking on "Remove now". So no emails on the server.

I also deleted (and I mean drag to the trash and emptied) both the /Library/Mail folder and its contents, and the /Preferences/com.apple.mail.plist file which holds all the accounts info in it.

When starting Mail it recreates the Mail folder, and when you create a new account the info is stored in the .plist file and the mail box folders appear in the Mail folder.

This did not solve the problem. As soon as I told it to check for mail I get the spinning wheel and end up having to force quit.

Interestingly though when I created a new user account and set up mail under that account from scratch it works fine!! wtf??

So the question is: What else do you have to delete to get Mail to think it is an entirely new setup? So far I have removed all of the following:
/Library/Prefernces/com.apple.mail.plist
/Library/Mail - the entire folder...gone burger!

Could it have something to do with the Address Book?
 
OK may have jsut answered my own question. I moved the /Library/Application Support/AddressBook folder onto the desktop and everything now magically works fine!!!

The Mac has even synced all my contacts back into the AddressBook.

Stunned but happy.
 
One by one I replaced each mbox, until only "MessageUidsAlreadyDownloaded" was the only one missing to be replaced, and Mail was still working, so I guess that's the sinner.

I have the same problem but I don't have a "MessageUidsAlreadyDownloaded" mbox... There is a text file with that name but it's one of the preference files...
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.