Did enabling administration through the Web Adaptor resolve the issue?
I have a situation where the ArcGIS for Server will not publish a map service (same error as original post) after registering the Web Adaptor. Publishing works fine up to that point. Even un-registering the Web Adaptor afterwards makes no difference. It's as if the Web Adaptor registration corrupts something in the server.