I do receive the same error message as Jake in my environment.
It seems to be a problem with the proxy, which is a proxy with authentication.
Even if the service account user of portal is allowed to access the internet via proxy, it does not work correctly.
The error message is extremely confusing and does not provide any guidance as to what the underlying issue is.
To troubleshoot this I had to reproduce this issue with the browser dev tools open and inspect each response of the network calls manually. There I was able to see some errors around proxy authentication issues.
From there we configured our Portal server to go through our proxy server for server side calls, see - Configure your portal to use a forward proxy server—Portal for ArcGIS | Documentation for ArcGIS Ent...
I also had to work closely with our network infrastructure team to to make sure that the domains of the AGS services we were trying to use were whitelisted on the proxy server too. Hope this helps.