Based on the REST Services directory, you have an ArcGIS Server 10.0 without any Service Pack installed. I also noticed that the your map Service does not have the legend resource link. This returns the legend information for all layers in the service.
You need to install at least Service Pack 1 for ArcGIS Server 10.
One of the issues addressed with this service pack:
REST API For .Net
NIM058419 - Add support in .NET REST for generating MapService LEGEND/TOC.
But Esri recommends that all ArcGIS 10 customers download and install the latest Service Pack at their earliest convenience, to ensure the highest quality experience when working with ArcGIS 10.