Since the roll-out of the new Add item interface in AGOL, we've seen some buggy behavior while adding feature services from ArcGIS Server. In particular, the error happens when storing credentials to the service in the item when adding to AGOL.
ESRI support was able to replicate the error and is working on a hot fix.
We aren't having the same issue adding map services, those seem to work fine.