Can you provide the URL to the REST endpoint of your map service so that we can take a look? Alternatively, if you have a web map that you've made in ArcGIS.com that you can share publicly, we can get the URL from that too.
One idea that may be the problem is: if your GIS server is not public (e.g., behind a firewall), ArcGIS.com won't be able to generate legends for any services. This is because the utility that generates the legend requires access to the map service. You will be able to view the map service display in the ArcGIS.com map viewer because you're browser is running inside your firewall, and thus can see it. The browser views the service directly and doesn't go through ArcGIS.com.
Thanks,
Mike