I tried your attached webmap json, but instead of producing a legend with correct classes an image with no legend was produced. I made 1 small modification to your json, adding the 'id' property back to the 'layerDefinition' object (the webmap json that get's posted by the esri print dijit does this as well), and received the same results as before: a legend with the default symbol.
Any other Ideas?
I've attached the new json.
Thanks,
-Alex