"Relaying not permitted"

I get a "Relaying not permitted" here when I call mail($to,$subject,
$message,$headers); from php.
The thing is though, the mail goes through no problem when I leave out
the headers .... mail($to,$subject,$message);

Why does adding the headers cause a relay condition here ?

Thanks...

$headers = 'From: webmaster@example.com' . "\r\n" . 'Reply-To:
webmaster@example.com' . "\r\n" ;

# ERROR LOG

Return-path: <>
Envelope-to: posted@rs3.whbdns.com
Delivery-date: Tue, 22 Jan 2008 14:05:11 +0000
Received: from mailnull by rs3.whbdns.com with local (Exim 4.68)
id 1JHJkT-0001Yt-E8
for posted@rs3.whbdns.com; Tue, 22 Jan 2008 14:05:09 +0000
Auto-Submitted: auto-replied
From: Mail Delivery System <Mailer-Daemon@rs3.whbdns.com>
To: posted@rs3.whbdns.com
Subject: Mail failure - rejected by local scanning code
Message-Id: <E1JHJkT-0001Yt-E8@rs3.whbdns.com>
Date: Tue, 22 Jan 2008 14:05:09 +0000

A message that you sent was rejected by the local scanning code that
checks incoming messages on this system. The following error was
given:

"Relaying not permitted"

------ This is a copy of your message, including all the headers.
------

Received: from posted by rs3.whbdns.com with local (Exim 4.68)
(envelope-from <posted@rs3.whbdns.com>)
id 1JHJkT-0001Yq-B3; Tue, 22 Jan 2008 14:05:09 +0000
To: Posted Project <tom@gmail.com>, <jerry@gmail.com>
Subject: Contact Form Submission
From: webmaster@example.com
Reply-To: webmaster@example.com
Message-Id: <E1JHJkT-0001Yq-B3@rs3.whbdns.com>
Date: Tue, 22 Jan 2008 14:05:09 +0000