Mail sent by user nobody

Hi,
I got a customized php program made for me that handles my sales database.
Whenever I click on an item that it has been shipped, it emails the customer to say that the item has been shipped.

I have recently changed web hosts (from 1 shared host to another), and now the customers are not getting any emails
So to try troubleshoot the problem, I created a simple php file with the following code:
<?php
$to = "[myemail]@gmail.com";
$subject = "Test mail";
$message = "Hello! This is a simple email message.";
$from = "[myemail]@gmail.com";
$headers = "From: $from";
mail($to,$subject,$message,$headers);
echo "Mail Sent.";
?>
(I just put [myemail] instead of my actual email address for the sake of this post only)

And lo and behold, I am not receiving any emails either.

So I contacted my host provider and he told me that he can see the following error in the mail log:
R=checkspam2: Mail sent by user nobody being discarded due to sender restrictions

So my question is, how do I (or what do I tell my host to do) to fix it?

Thanks in advance

 

$from_email = "enter your email here";

$email_headers .= "Content-Type: text/plain \r\n";
$email_headers .= "From:". $from_email . " \r\n";
$email_headers .= "Reply-To: <".$from_email.">" . " \r\n";
$email_headers .= "Return-Path: <".$from_email.">" . " \r\n";

$email_headers .= "Message-ID: <".time()."-".$form_email.">" . "\r\n";
$email_headers .= "X-Mailer: PHP v". phpversion() . "\r\n";
$email_headers .= "MIME-Version: 1.0 " . "\r\n";
$email_headers .= "Content-Type: text/plain; charset=iso-8859-1" . "\r\n";

 

The second-last post on this page appears to address your issue: http://www.karakas-online.de/forum/viewtopic.php?t=9715

Also see: http://forums.cpanel.net/f43/sent-u...er-restrictions-whm-tweak-settings-75613.html