Just in case anyone is still looking, our problem still exists. Here's where we are at now..
We can print ANY non secured service just fine.
We can occasionally (when the stars align, or we sacrifice a goat or some other strange occurrence) print secured services.
What we have done:
We are right up to date with 10.2.2 which helped. One of our main users had a "-" in it so we needed a patch.
I managed to get the JSON for a handful of layers so I can paste it directly into the REST end point and it still fails.
We republished the service as per: ArcGIS Help (10.2, 10.2.1, and 10.2.2) And it still fails.
What we are currently investigating:
Web Tier authentication (we have doubts it will work with our security and data accessibility mandates though).
The core of our problem seems to be that we have a publicly accessible webmap that uses a handful of layers that need to be secured (so people can't scrape the data for themselves), but don't need to have a login for the map. We are pretty sure we can get it to work if we make everyone log in, but it isn't feasible for a public map.