Здравствуйте! Написал функцию для работы с mail():
function mailer($email, $subject, $msg, $from = false) {

// $msg = iconv("utf-8", "windows-1251", $msg);
// $subject = iconv("utf-8", "windows-1251", $subject);
if (isset($from) && is_array($from)) {
$name = $from[0];
$from = $from[1];
}
$headers = "MIME-Version: 1.0\r\n";
$headers .= "Content-type: text/plain; charset=\"windows-1251\"";
$headers .= "Date: ".date("Y-m-d (H:i:s)",time())."\r\n";
$headers .= "From: \"$name\"<$from>\r\n";
$headers.="Subject: $subject";
$headers .= "Content-type: text/plain; charset=\"windows-1251\"";

if (empty($from)) {
$headers .= "X-Mailer: My Send E-mail\r\n";
}
else {
if (empty($name)) $name = 'unknown';
$headers .= "From: \"$name\"<$from>\r\n";
$headers .= "X-Mailer: My Send E-mail\r\n";
//$adds .= "X-sender: ".$from."<".$from.">\n";
}

return mail($email, $subject, $msg, $headers);
}

Вызываю ее так:
$res = mailer($aemail, 'Новое обращение с сайта '.$server, nl2br(strip_tags($_POST['msg'])), out($_POST['email']));
if ($res == TRUE) {
$_SESSION['time'] = time();
echo 'Сообщение успешно отправлено!<br /><br />';
}
else {
echo '<p class="text"><span class="error">
Ошибка отправки сообщения!
</span></p>';
}

Пишет: Ошибка отправки сообщения!
В чем моя ошибка?

Была у меня проблема, но оказалось, что проблема не у меня, а у сервера. Так что попробуй заюзать этот класс ТЫЦ!