Проверьте работает ли вообще функция mail на сервере:
echo "Testing" | mail -s "Test"
test@example.com
Проверьте установлена ли почтовая служба: sendmail, postfix или другая.
Проверьте запущена ли почтовая служба.
Для sendmail/postfix проверьте настройки в php.ini:
; For Unix only. You may supply arguments as well (default: "sendmail -t -i").
;
http://php.net/sendmail-path
sendmail_path = "/usr/sbin/sendmail -t -i"
Проверьте в php.ini не внесена ли функция mail в список запрещённых функций:
disable_functions