We've been experiencing the same issues with our Javascript Webmap Applications as well. Since about version 3.3 or 3.4 of the Javascript API the legend that was appearing on our PDF printed maps has completely disappeared.
Stranger still, even if we print using the default Webmap Applications provided by ArcGIS Online, we still don't get a map legend.
What happened to our map legend.