I am having the same issue and I have created my own custom MXD templates to use for the print task. I have built a blank legend and the legend gets built once it is exported to a pdf based on what layers are visible. The link you included was what I used to make my custom MXD templates and create the geoprocessing service. However, it never mentions anything about how to set up the legend to get it the way legend2.JPG is set up. If anyone has figured out how to do this properly, please reply with a solution. Thanks.
Hello Evan,
You can test the Legend behavior directly on the custom MXDs , just need to add the services to ArcGIS Desktop.
If you right click on the legend element and go to properties, you should see all the legend properties.