I assume you've also disabled all the usual suspects - ipv6, SELinux & firewall? Just for confirmation, can you run the following on the new server:
Code:
host `hostname` <-- type as-is with backticks not single quotes
dig yourdomain.com mx
dig yourdomain.com and
and post the output.