mail() returns a boolean value. What value is returned when you try to send it? To check, do something like this:
$mail = mail($to, $subject, $message); // fill in appropraite variables, etc.
var_dump($mail);
EDIT: Also, what O/S is your webserver on? When you do a phpinfo(), what values do you see for "sendmail_from" and "sendmail_path" ?