If its outbound mail double check the SMTP settings, make sure you are using port 25, and you may need to use authentication depending on how the server is setup. Im willing to bet you its one of those 3 issues.
Following up on my Outlook adventure...
Could it be that the mail sitting there in the outbox may have been the fault of a corrupt pst file (the original one at install)? It appears that way. I triple checked the settings and found nor problems. It also sent test emails ok. Outbox email still wouldn't go. So I created a new pst and made it my default, restarted outlook and removed the old pst using data file management. After that I was able to send email no problem but his old emails, etc. were obviously not there anymore. So I imported them from the old pst file and then he had all his mail, calendar, and contacts and everything worked fine. I would not have thought that the pst would affect his ability to send email, but it seems that way. Interestingly, the 'import' brought in his old outbox emails and they still just sat there, but NEW emails got sent instantly. So he just deleted the old ones and sent new. It's all good now.
Anyway, thanks for the help guys... I learned a lot about PST files and Outlook in the last couple days. Seems like I could have just copied the outlook.pst file from his old computer and imported from that rather than exporting to a new pst file first.
Yeah PST's are horrible. We're in the process of setting up a mail archiving system so that we can get rid of them permanently. We had so many users with 10+GB of pst's because our exchange limits aren't big enough for their stupid attachments. Down with the PST's!