Are the nameservers for the server in question configured correctly? (/etc/resolv.conf) Does the server's base hostname resolve globally and does the server's base IP (eth0) have reverse dns properly configured for it?
These things can all contribute to what you've mentioned.