Issue solved.
This issue is due to the SSL certificate we used. It’s issued with an intermediary certificate (that we did not send), so on Shopify side they are not able to find the trusted root issuer because the SSL is missing the “middle part”.
The solution is include the intermediate certificate in the certificate file.