Problemas con mail()

[Kikoken]

Tengo el siguiente problema:
Ya he probado mi formulario enviandolo con mail() en un servidor, lo malo es que ahora he querido usar el mismo en otro host que está con Linux y PHP y no me pesca el envio, sin embargo ya verifique que las variables si las recibe
¿alguien sabria decir pq sucede esto? ¿es problema del servidor?