This print service is hosted on the Amazon Cloud (Amazon AWS). If you have an IT team that is monitoring web traffic, sometimes they will notice that you are getting a lot of traffic from these IP addresses such as 174.129.18.254
This IP address is where the print service is coming from. So anyway, IT doesn't see that its ESRI, just Amazon and the IP address ends up blocked by IIS, you will get that error. Some companies have it set up to block IPs automatically based on some kind of algorithm.
I also think there is something to do with the URL for your mapservice and the case sensitivity of the URL, make sure that's all well and good.
I end up seeing errors in the Print tool when there are more than 1000 features in my map view or if my map service is under heavy load and its not responding fast enough. So you will have to zoom into a closer area to get that print tool to work correctly.
Lastly, if you have data in the map that is scale dependent, I noticed that I would get print errors if the user was not zoomed in close enough to have all of the layers active. For instance at the initial view, if it was just a basemap and no dynamic content it would fail. Clearly very moody this thing....