I have a Dynamice service called TestService., the service map file has 3 layers. I am using ArcGIS server Silverlight API 2.1 and 2.2 (beta). In both version: I could not get the legend rest end point.
I don't think your API version is playing a part in your problems. I think it might be your version of Server. I didn't look it up so I'm a little shaky on the details but I think at version 10 the services has to be public and maybe at 10.1 it is totally exposed internally and externally. Not 100% sure so I would quickly look that up.