Did you guys get this working? It is very reliable once you get it setup correctly. One trick that may be causing you trouble is that the mxd template needs to be zoomed out to the full extent that anyone may ever ask for. I simply leave the templates zoomed out to world extent. Also, remember to leave all group layers on and turn off only the actual feature class layers in the template. This is necessary due to only the list of actual layers being sent to the service in the request, not group layers. The new print service at 10.1 will make this gp service no longer needed in most cases, and is MUCH faster. It will still be needed for large format printing (> 11x17) by using the data from SDE and not the web service (web service images will begin to pixel-ate at larger print sizes).
Hope that helps!