Hey,
There are quite a number of reasons this could be happening, but first of all I'd double check to make sure the mail() function is returning True - if you haven't already ...
PHP Code:
if(mail(your mail parameters)) {
echo "It works!";
} else {
echo "Failed :(";
}