I would try the following to start with:
Check the certificate to start with.... Just to isolate the issue, you can create a test AAD application, use the certificate and see if it works as well.
To isolate the issue, you can test the API call in Microsoft Graph explorer as well...
BTW i am using the certs and its working for me. I dont face any issue as you point out.