It sounds like a server configuration issue. After you try to send an email you can go to a page that has this code on it:
View source on that page and the email headers will be listed. You can copy those and send them to the hosting provider to ask what is wrong with the header exactly.
You can also try using the checkbox in the email object settings for "use additional headers" and see if that helps.