I came across this issue yesterday and it took a bit to figure out. Thought I would post it here to aid others.
We have two ArcGis servers and a web adapter setup. ArcGis servers on running on the default cluster.
When I submitted a print job, I received the following error on all my MapServices.
Unable to complete operation. Error executing tool.: Layer "layer1": Unable to connect to map server at http://....
Turned out the two user that the ArcGis servers were running under did not have permission to see the Web adapter server. Once I added the ArcGis NT User to the group that has access to the Web Adapter server, all was well.