Hi Tom,
have you tried to check the ArcGIS Server log? if your map service is secured the possibilities cause are ssl, cross domain, or something that make the token is invalid.
the following are samples message related with printing tools service failed
1. if your certificate or cross domain setting not configured properly
The host name in the certificate is invalid or does not match (WinINet ERROR_INTERNET_SEC_CERT_CN_INVALID, 12038), URL = https://gisserver/arcgis/sharing/generateToken/
2. if your GIS Server network (printing tools services) cannot access your map services. for the example below, I have GIS Server machine (local) but doesn't have internet connection. in the other hand client application consumed online map service as basemap. printing tools failed due to the machine cannot access online map service.
Error executing tool.: Layer "defaultBasemap": Unable to connect to map server at http://services.arcgisonline.com/ArcGIS/rest/services/World_Topo_Map/MapServer........Failed to execute (Export Web Map). Failed to execute (Export Web Map Task).