Sounds to me like you are not logged into your regular ISP's system. I get the same error when logged in at work, and trying to send email with my normal ISP's SMPT settings. Many mail severs will not relay outside their own mail system, to avoid being used by spammers and the like.
If what i have described fits your situation, try setting the SMPT server settings to the one where you are logged in.
Of course if it doesn't allow relaying of messages, you will have the same problem. I use the web based mail service from my ISP when I am at work and not sending from an IP adress within My ISP's network.
Good luck, and Happy Computing