Que tal
ASYNTETYCO, revisaste que la dirección de destino sea la correcta?, verifica que las variables que envias sean las correctas, si te sigue dando problemas y teniendo en cuenta la respuesta de tu hosting de que todo esta bien configurado yo te recomendaría que utilizaras la librería
PHPMailer
Saludos.