access to the exchange server denied

I have created a webservice that accesses ms exchange via coldfusion.
I have a ms exchange installed on a server and coldfusion installed on a server.
When I test the web service from the server where coldfusion is installed, I am able to successfully execute the logic and access exchange.
When I test the web service from a separate server I receive an "access to the exchange server denied". The user name and password that I am using to access exchange is the same.

My network staff has assured me that the relay permissions between the three servers exist.

Any ideas on what may be causing this?