So I encountered this issue (which I managed to resolve), and wanted to share the problem and solution, in case someone will experience the same issue.
The problem:
Additional information:
What else can cause this issue?
In my case,
The issue was with the enhanced key usage of the certificate, that was set to "server authentication".
When I issued the certificate, via the CA server of my org, I used a predefined web server template that had set the key usage to the above.
Issuing a new certificate with "client authentication" usage resolved the issue for me.
Hope it will help someone else who encounters a similar issue.