WCF Error : 'It is likely that certificate 'my cert' may not have a private key that is capable of key exchange

I had this problem, and it turned out that the account the service was running under did not have permissions to access the certificate's private key.

Here are the steps I used to solve it:

• Start the Cetificate manager. Do this by running MMC, activate [File]-[Add/Remove Snap-in...], then add "Certificates", selecting "Computer Account" and "Local Computer" in the ensuing wizard dialogs.
• In the certificate manager, right-click on the relevant certificate and activate [All Tasks]-[Manage Private Keys]
• This gives you a permissions window. Click Add
• Add the account name or group that this service runs under.

Seems like your certificate was created for signatures and not key exchange, what I suppose to be normal for SSL certificates.

If you look at the makecert documentation, you can see that the -sky switch lets you specify whether the certificate should be used for signatures or key exchange. You can try to create a self-signed certificate with type exchange and test whether the exception still occurs. Don't forget to put the self-signed certificate into the machine's trusted root certification authority folder in order to avoid exceptions that the certificate is not valid.