This usually happens when you don't have your outgoing mail server settings correct...
Do you have "my server requires authentication" (or something of that nature) checked off in your mail client? You should. You should also be using the same login info that you use to download email.
Our smtp server doesn't allow relaying mail for anybody who doesn't authenticate with it first to help prevent spammers from using us to send spam!