Typically, this means there is a problem with the listening port specified or the relay connection setup inside of Exchange. Below are a few things that you can check with your Exchange Server configuration.

1. Make sure your ports are open on Exchange and listening.
2. Open a Command Prompt window on the Exchange Server and run this command: Netstat -abno >>Report.txt This will generate a report of all ports active and listening on your Exchange Server. The report file is created in the current directory of the Command Prompt window.
3. Ensure you can telnet into your Exchange Server using SMTP port (default is 25).
4. Open a Command Prompt window and run this command: telnet hostname.domain.com 25 (if you are using default port)
5. Run simple EHLO commands to see if you get a reply back. If response is Hello, proceed to next step.
6. Test connection using a blank SMTP password. If you receive a relay error, this indicates a problem in Exchange. Use entire email account as username. (I.E. example@domain.com) This account must be set up in Active Directory and Exchange.
7. You will want to create an anonymous relay on a Receive connector. (For procedures follow http://technet.microsoft.com/en-us/library/bb232021(EXCHG.80).aspx)

Note:

Please consult your Exchange Administrator to comply with security procedures in place. Relay Connectors can be configured with many different authentication types.