Have you ever seen this when adding a secured service as an item in ArcGIS Online?
When it asked me for credentials, and I selected the "Store credentials with service item" option.
I am quite sure the credential is correct, because if I copy and paste the service URL directly into the address bar in the browser, I can use the same login to unlock the service and see the service details.
I noticed "ArcGIS Online supports ArcGIS Server authentication (not Web Tier authentication) for adding and accessing secure services."
Security Configuration Settings
User Store:ArcGIS Server
Built-inRole Store:ArcGIS Server
Built-inAuthentication Tier:GIS Server
Authentication Mode:ArcGIS Tokens