Did you remember to punch in your username and password for the SMTP server as well? The interface in preferences kinda makes it look like you don't need to put it in twice, but you do. The fields on the main page are only for the incoming server.
I called apple, they had me delete my mail account in the librarys folder, and let OSX create a new Mail app, or whatnot. Everything seems to be just fine now.