se que es medio tarde y obviamente ya debes haber solucionado tu problema, pero nunca esta de mas probar....
para mandar un email con formato html tenes que agregarle las cabecera que indica que el mensaje esta en este lenguaje:
Código PHP:
$nombre = $row ["nombre"];
$mail = $row ["mail"];
$mensaje = $_POST ["mensaje"];
$sfrom="tuweb <[email protected]>"; //cuenta que envia
$sdestinatario="$mail"; //cuenta destino
$ssubject="Newsletter de Aqui el nombre de tu web!"; //Asunto
$shtml="
<html>
<body>
<div style='color: #FF0000'>
Estimado ".$nombre.", \n ".$mensaje."
</div>
</body>
</html>
"; //mensaje
$sheader="From:".$sfrom."\nReply-To:".$sfrom."\n";
$sheader=$sheader."X-Mailer:PHP/".phpversion()."\n";
$sheader=$sheader."Mime-Version: 1.0\n";
$sheader=$sheader."Content-Type: text/html";
mail($sdestinatario,$ssubject,$shtml,$sheader);