We ran into this issue today. Our intermediate and root certificates were not setup correctly on the IIS host running the web-adaptors and portal product.
We have the ArcGIS Server (AGS) and datastore on a separate host. After fixing the intermediate and root certs on the IIS server, we were able to publish to the AGS directly as a full featured map service (not a hosted feature service), however we still were unable to publish hosted feature services to the portal data store. Since we could publish to the AGS, that ruled out the issue with server and data store.
We restarted the IIS and portal windows services many times and spent a few hours troubleshooting but kept receiving this error. The final fix was to reboot the entire VM, when it came back up the certs were trusted from portal and we were able to publish the hosted feature services. I would have thought that restarting the windows services would have been enough, but something underlying was still caching the issue with the cert chain.
I'm not saying this is your problem, just providing feedback on how we resolved it in our environment (4+ hrs of troubleshooting).
We also have a web-app firewall in the front of this environment and a firewall between the IIS/Portal server and AGS+Data Store in the mix that was causing a few issues (false-positive denies). Those FW issues were resolved early in the day, but the publishing did plague us until we got the intermediate/root certs loaded correctly AND completed a server reboot.
Best of luck.
