Paul,
That seems like a generic 'connection failed' type of message. Please open a command window on the Orchestrator server and attempt to telnet to the mail server. If it connects it should display an empty box, if it fails it will eventually fail as shown below:
This failed as I used the wrong port.
If this fails you will need to work with your networking team to ensure the orchestrator server has access to the mail server