Have you tried a simple mail script to make sure that the php mail() function is working?
echo "email sent";
echo "email failed";
Upload it to your server and open up the file through a browser. What happens?