We experienced the same issue, we changed our ProviderUri on the SharePoint to https://login.microsoftonline.com//wsfed" we:
https://login.microsoftonline.com/<tenantID>/wsfed
We also had to add the ssoSSO certificate into the trusted root of the app and front end server.