Try sending a very simple test e-mail... mail('myaddress@mydomain', 'test', 'test');
See if you receive it. If not, chances are sendmail isn't configured properly on that server.
If the e-mail DOES send, there might be a problem with the Unix server converting line breaks. Try sending your message without using multiple headers (i.e. just use the "From:" header).
If that works, the Unix server may be incorrectly converting LF's to CRLF automatically, erroring when you send CRLF (get's converted to CRCRLF). To test this idea, use multiple headers, but only use a LF ("\n") to separate them.