Probabilmente non hai impostato correttamente le intestazioni del messaggio.

Perchè non utilizzi una classe tipo phpmailer che è ampiamente testata?