Check your "Path to Sendmail" environment variable in your php.ini file for starts. Likewise you can check it with <?php phpinfo(): ?> in a script.
If the path is blank, make the change in the .ini file to point to it. If everything looks like PHP can find sendmail... then it could actually be a sendmail problem. That is a topic for another forum 🙂
Another good thing to try is to telnet into the server and actual send a message out using pine or something to make sure you CAN send mail from that server.
Tim Frank