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.