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

I have a WCF service I'm trying to host on our production web server (IIS6). I've set the web up and tied our cert to the web. When I try to browse to the service url, I receive the following error in the event log :

The exception message is: It is likely that certificate 'CN=.mydomain, OU=Secure Link SSL Wildcard, OU=I.T., C=US' may not have a private key that is capable of key exchange or the process may not have access rights for the private key. Please see inner exception for detail.. ---> System.ArgumentException: It is likely that certificate 'CN=.mydomain.com, OU=Secure Link SSL Wildcard, OU=I.T., O=mydomain, C=US' may not have a private key that is capable of key exchange or the process may not have access rights for the private key. Please see inner exception for detail. ---> System.Security.Cryptography.CryptographicException: The handle is invalid.

I've confirmed ASP.Net 1.1, 2, and 4 are all set to 'Allow' in 'Web Service Extensions'. I've also confirmed the cert is set up in iis and it shows 'You have a private key that corresponds to this certificate'. Also, Execute Permissions are set to 'Script and Executables'.

Solution

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.