Por qué .. lo más seguro es que lo estés enviando en formato HTML.
En HTML los salto de línea no son \n sino tag <br> ... para ello puedes usar (para no modificar tu texto actual)
Código PHP:
$mensaje=nl2br($mensaje);
(al final de ese código y antes de atacar el resto de tu mail() ..)
Un saludo,