The bug that Drew mentioned applies to me. We are on 10.1. Here is what I've got and how I got around it.
I have a map service and a custom print service within a secured folder. I am able to print the map if I print the entire dynamic map service. I can even set the visibleLayers property to hide some layers. As soon as I try to print an individual feature layer from this map, it doesn't work. I have tried the exact same thing on an unsecured map service and it works as expected.
I wanted to print an individual feature layer so I could set the selectionObjectIds property in my webmap JSON to highlight a particular feature. As a work around, I added a graphics layer to the webmap JSON. I grabbed the selected feature's geometry and used that to define the graphics layer.
We can't upgrade beyond 10.1 just yet. Hopefully this helps someone.