Проверьте работает ли вообще функция 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