I had been dealing with this issue and I'm using a self-hosted WCF service. I just made the breakthrough:
I had a certificate in the personnel folder for the Machine store. It expired and my manager issued a new one. The new one failed for me with this error. I tried a lot of stuff from Google but in the end, resolved the issue using a completely different solution.
I installed both certificates- the expired one and the newer one. Then I used this command to get a list of them:
certutil -store My
I get this output (info is fake and other certificate are not listed):
================ Certificate 1 ================
Serial Number: 6d
Issuer: [email protected], CN=VoiceTrust Server CA, OU=VoiceTrust Oper
ations, O=VoiceTrust
NotBefore: 03-Jan-2013 3:33 PM
NotAfter: 03-Mar-2013 3:33 PM
Subject: [email protected], CN=hornet.voicetrust.com, OU=Software Develop
ment, O=VoiceTrust eServices MENA FZ LLC, L=Dubai, C=AE
Non-root Certificate
Cert Hash(sha1): 98 5f a0 d3 11 6a 4b 64 3b db 0a a4 11 66 fc 08 28 74 7e 53
Key Container = {E5BC0912-7808-4B89-B457-31946DE5990E}
Unique container name: dfedfcc149408fb990a3bacd6d31126b_3277b2c9-9894-46d0-9b6
4-30f0d6589239
Provider = Microsoft Enhanced Cryptographic Provider v1.0
Private key is NOT exportable
Encryption test passed
================ Certificate 2 ================
Serial Number: 6d
Issuer: [email protected], CN=VoiceTrust Server CA, OU=VoiceTrust Oper
ations, O=VoiceTrust
NotBefore: 03-Nov-2013 3:33 PM
NotAfter: 03-Dec-2013 3:33 PM
Subject: [email protected], CN=hornet.voicetrust.com, OU=Software Develop
ment, O=VoiceTrust eServices MENA FZ LLC, L=Dubai, C=AE
Non-root Certificate
Cert Hash(sha1): 30 5f a0 d3 11 6a 4b 64 3b db 0a a4 11 66 fc 08 28 74 7e 53
Key Container = {E5BC0912-7808-4B89-B457-31946DE5960E}
*Unique container name:* 55edfcc149408fb990a3bacd6d31126b_3277b2c9-9894-46d0-9b6
4-30f0d6589239
Provider = Microsoft Enhanced Cryptographic Provider v1.0
Private key is NOT exportable
Encryption test passed
Now, everything seems OK but certificate 1 is expired and works if I try to bind it to a port whereas Certificate 2 fails with Error 1312.
The key difference that baffled me was the Unique container name property. It should be representing a physical key file on the hard drive in the %ProgramData%\Microsoft\Crypto\RSA\MachineKeys\
For Certificate 1, the file was there but for Certificate 2, there was no such file. After searching I found the file against Certificate 2 in the sub folder of %AppData%\Microsoft\Crypto\
folder. That's user specific keys not Machine level keys. It's amazing that the certificate is being imported into Computer store yet it always keeps the container key of User's store.
I deleted the '55edfcc149408fb990a3bacd6d31126b_3277b2c9-9894-46d0-9b64-30f0d6589239' file under the AppData folder and ran the repair command for my certificate 2 on the store:
certutil -repairstore My 2
This time, the Unique container name was reflecting a file in the proper folder under '%ProgramData%\Microsoft\Crypto\' and everything started working.
Hope this is helpful to someone.