After upgrading to Portal for ArcGIS 10.4, this problem has gone away. I think the solution involved two things. First, our forward proxy does cause issues when trying to store credentials. I never go the proxy config settings to work correctly, but for now, whitelisting the sites has solved that problem. Second, even this only worked after upgrading to 10.4, so I have to assume that there was a bug in version 10.3 causing a problem.