Ok, I flipped some settings on the server - I can get my KML to render. I tried yours again and see it:
I can get the legend to render with the map service:
KML layers should be supported... I'm still not sure why it wouldn't show for the KML. I started debugging the legend.js API file and didn't hit key spots that would construct the legend, but there wasn't a clear, obvious reason why. Perhaps it's a bug in the API? Are there any examples showing this working? I couldn't find one...