I had the same problem today. I found that using the token parameter on my map service URL worked.
1. Create token on behalf of the user identity with Identifier set to http://www.arcgis.com
2. Include that token value on the Map Service URL that is being added to an ArcGIS.com map.
Example URL with token as a parameter:
http://arcgisserver.domain.name/ArcGIS/rest/services/mySecureService/MapServer?token=6xgjHf9MIcnI1u8.....
David, Dan,
What version of ArcGIS Server are you running? Was it working before and stopped, like maybe after you upgraded?
Thanks
Mike