It sounds like your SMTP server is not configured to allow relaying. What or who are you using as an SMTP server?
In the Admin area, look under Email Settings.