I assume quitting and relaunching mail did not help?
checked with Connection Doctor? (paste output)
tried deleting the mail passwords from keychain? (delete send and receive, quit and relaunch keychain access, delete them again if necessary, which sometimes is)
web access to email send/receive ok? (this is a really good troubleshooting step if available)
I work for the Department of Redundancy Department
