I'm having the same problem (when I add a secure map service from ArcGIS Server, it won't accept my credentials). This used to work for me, so I'm wondering if some of the recent changes in AGO may have broken the functionality? We're running ArcGIS Server 10.01. While setting up a token and then securing the resulting web map works, the downside for me is that our secure services let users authenticate against our active directory (meaning that any staff member of my organization can view the map after logging in), whereas a secure AGO map requires everyone who needs access to it to create an account with arcgis.com and be granted access to that specific map.
For an organization of over 3,000 people, it is much preferable to use our own security and have AGO just pass the credentials on rather than requiring everyone to use AGO accounts.
I should also note that I have no problem connecting to our secure services via ArcMap.