I've experienced a similar issue and found the problem to be that the "layoutOptions" property of the print template MUST be specified for the legend to be definitely included in the printout. Maybe it was just an isolated instance of the issue, but it sure worked for me. I also tested it with Esri's latest version of the print service (http://utility.arcgisonline.com/arcgis/rest/services/Utilities/PrintingTools/GPServer/Export%20Web%2...)
Regards
Frederick