Mira; despues de un consejo de cluster que lei, en el que decia que lo mejor para el mail es instalar la clase phpmailer, asi lo hice
y se acabaron todos los problemas de enviar mails.
A parte de todas las ventajas que tiene puedes mandar mails con formato html , archivos adjuntos y enfin mejor lo ves.
Aqui tienes un tutorial en español, veras que es muy facil
http://www.programacion.com/php/articulo/phpmailer/
un saludo