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?