Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
I've experienced similar problems, although it might have been the other way around with incoming working and outgoing not. I'm afraid I dont' remember the details but what created the problems for me seemed to be that I was using a BT server for incoming/outgoing, which worked fine while I was connected to the internet through BT but not when traveling and using other ISPs. Some kind of authentication issue I guess. Haven't had an of those problems though since I switched to gmail (which I got set up with Mail as well).

Might be useful knowing what your settings are, especially for authentication?
 
Mail problem solved (for now)

Changed the port number in Mail preferences. Apparently, it had changed (I don't know if I did it of not), but anyway, incoming mail working now. I have my Verizon web mail as backup.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.