Trata de poner una codificacion forzada en tu variable $mensaje y cambia la codificacion de tu mail por charset=ISO-8859-1.
Puedes probar con esto:
Código PHP:
$mensaje = utf8_decode($mensaje);
//esto para la otra prueba
//$mensaje = utf8_encode($mensaje);
Recuerda que utf8 tiene eñes y acentos codificados... y por lo tanto si envias un mail con utf8 los va a mostrar codificados.
Suerte!
