Had the same problem. I realized that my website host didn't allow me to 'send' mail through their servers (probably for spam prevention). So I had to set my Outgoing Mail to my internet provider's SMTP server. Worked like a charm after that.
If that's not the case (and it's probably not if you're mailing through your ISP) then you may want to go to TOOLS --> ACCOUNTS, click the mail tab, choose the account, click properties, click the Servers tab and check to see if the settings are correct. Consult your ISP for proper settings.
BTW - If you are 'receiving' e-mail then it's definately an SMTP problem.