Avevo lo stesso problema, poi ho inserito nel php.ini il server di posta in uscita che utilizzo e il mio indirizzo e-mail ed è andato :-)

Cerchi nel php.ini la riga [mail function] e poi hai il seguente, e lo imposti a dovere:

codice:
[mail function]
; For Win32 only.
SMTP = serversmtp

; For Win32 only.
sendmail_from = tuamail
tuamail chiaramente corrisponde al server che hai inserito.

Prova magari anche a te funzionerà