Este problema te lo da porque seguramente tu PHP no esta configurado para enviar mail, necesitas editar el archivo php.ini y buscar:
;sendmail_from =
[email protected]
Le quitas el ; del principio y cambias la cuenta
[email protected] por tu cuenta de correo.
Nota: Tu script para envio de correos parece ya no tener problemas, en cualquier hosting "decente" debe funcionar.