Are you using domain names or ip addresses to connect to the server? If domain names, verify that they resolve correctly.
I know with sending, you can telnet to the server and issue smtp commands directly. This will allow you to send messages to the server mailboxes, not external ones.
Last, some ISPs now block mail relay as a method of controling spam. If you are not on the same network, you may have the ISP blocking the traffic.
As for the linux part, I can't help you with that too much.
Good luck.