Create a test script


test.php

Code:
<?php

mail("[email protected]","Testing","Testing");
echo "finished at " . time();

?>
Upload the file to server, run it by going to url

http://yourdomain.extn/test.php

See if it can send mail. Also check mail server log if there any entry when you access the page.

I only faced similar problem with wrong php.ini settings. So double check phpinfo show same setting for both sites.