Using mail() causes 504 Gateway Time-out in Nginx
Sounds like a problem with the ability for php to contact the mail server. Have you verified the following:
Iptables is off (or any other firewall for that matter)
Display the contents of the following:
Sendmail cfg
and the output of the following command
netstat -punta
(not calling you a name here ;) )