Your domain must have a SPF record in place. This specifies the servers that are allowed to send email from your domain. It sounds like your web server is on a different IP address from your mail server. You could either get your SPF record edited to include the web server address, or change your site settings to send email using your mail server rather than directly from the web server.
