Solved! Go to Solution.
See this tutorial on how to print from the source vector data instead of cached tiles.
http://resources.arcgis.com/en/help/main/10.1/#/Tutorial_Basic_high_quality_web_map_printing_exporti...
Instead of retrieving the tiles and stitching them together, the Print GP will make a /export map request to the service if it's a 10.1 service that has dynamic layers enabled on it. This will result in a new image being created from the data since /export will go to the data in this case. In all other cases, /export stitches the cached tiles together.