We are having the same problem. Our Dynamic layer is not public, but ArcGIS 10 SP 1 is installed. We are still not seeing any symbology. Does the layer have to be public if you have 10 sp 1?
In addition, we have learned the following:
1) Our layer are consists of 1 parent and multiple child nodes in the Legend TOC. The TOC part of the legend allow us to expand the parent layer (that is the group layer), but we cannot expand the child node (layers underneath parent group layer) to see the symbology
2) When we created a test FeatureLayer pointing directly to one of the child layers and all the symbology displays for that feature. Its like the legend won't work for dynamic layers when they are not public???