Prueba a ver si está funcionando mail():
Código PHP:
//Utilizo la funcion de php para enviar el correo
if(mail("$mail","$asunto","$mensaje","From: ".$tumail)){
echo "Gracias por tu envio <b>$nombre</b> Tu mail ha sido enviado a <b>$mail</b>";
}else{
echo "Error 001: No se pudo enviar el mail a <b>$mail</b>";
}
Saludos
