I, too, am using ArcGIS for Server 10.1 with secure map services. When I attempted to add a secure map service directly to an ArcGIS.com map via the >Add >Add Layer from Web button, the attempt failed.
I was informed by Esri Tech Support that I needed to log into our subscription, go to the My Content area, click on the Add Item button and add the secure map service to a My Content folder. Then, you can open your map and Add the secure service from your content folder. Tags/keywords added to your map service make it easy to find using the Search for Layers option in the map.