You've got a routing issue or an internal DNS issue - if your server has a public IP or resides in a DMZ, make sure your firewall rules allow and route from private address to DMZ/Public IP address of mail server.
Originally Posted by gilbertonunes36
if the mail server is on the same subnet (has a private address on your lan) then make sure the clients aren't trying to go out the firewall and accessing it via the public IP address. if that's the case - add an entry to the clients hosts file or correct the DNS to point to the private address from within the private LAN
8.0.3 UBUNTU10_04 UBUNTU10_04 NETWORK
8.0.3 UBUNTU10_04 UBUNTU10_04 FOSS