We are having the same issue, but with a javascript app. My feeling is that this has to do with the print service as well, and not necessarily the environment, though. I was originally thinking that messing with the legend settings in the template mxd might fix the problem... but no luck there.
I'd use create an arcpy script, publish that as my custom printing service and use that with my PrintTask in my web app.
These are what arcpy script would do:
- calll ConverWebMapToMapDocument() with your layout template to create a mapdocument object
- use LegendElement and apply legend style of your choice
- export to pdf or any other format
here are some help links help you with the script.
http://resources.arcgis.com/en/help/main/10.1/#/Advanced_printing_for_web_maps/01540000056t000000/
http://resources.arcgis.com/en/help/main/10.1/#/Tutorial_Basic_high_quality_web_map_printing_exporti...
http://resources.arcgis.com/en/help/main/10.1/#/ConvertWebMapToMapDocument/00s30000006n000000/
http://resources.arcgis.com/en/help/main/10.1/#/LegendElement/00s300000041000000/
http://resources.arcgis.com/en/help/main/10.1/#/ExportToPDF/00s300000027000000/
hope this helps.
If you happen to have the python code to share with us that'd be great!