“The private key for the certificate that was configured could not be accessed.”

I'm trying (and failing) to replace the certificates for an ADFS 2.0 stand-alone installation. I've generated the certificates and placed them in the local machine store. But, no matter what I do, I inevitably end up with the same error being reported when ADFS starts:

During processing of the Federation Service configuration, the element 'signingToken' was found to have invalid data. The private key for the certificate that was configured could not be accessed. The following are the values of the certificate:

Element: signingToken

Subject: CN=signing certificate

Thumbprint: <snip>

storeName: My

storeLocation: 0

Federation Service identity: NT AUTHORITY\NETWORK SERVICE

…

User Action

If the certificate was imported from a source with no private key, choose a certificate that does have a private key, or import the certificate again from a source that includes the private key (for example, a .pfx file).

If the certificate was imported in a user context, verify that the store specified above matches the store the certificate was imported into.

If the certificate was generated by a certificate request that did not specify the "Machine Key" option and the key is marked as exportable, export the certificate with a private key from the user store to a .pfx file and import it again directly into the store specified in the configuration file. If the key is not marked as exportable, request a new certificate using the "Machine Key" option.

If the Federation Service identity has not been granted read access to the certificate's private key, correct this condition using the Certificates snap-in.

Well, I've followed all of the above suggested user actions, and none of them have resolved the issue. I also can't seem to find any advice from anyone else for what diagnostic steps to take next. So, what do I try now?

I'm getting 5 errors when I restart. The first four are as above, with little variations: First for Element: serviceIdentityToken and the service communications certificate, then encryptionToken, additionalEncryptionTokens, and signingToken for the certificate I want to use for decryption and signing, and finally:

There was an error in enabling endpoints of Federation Service. Fix configuration errors using PowerShell cmdlets and restart the Federation Service.

I presume this fifth error relates to the first four, but if not, I can add more details for it. Both the SSL and signing certificates were generated by our domain CA.

I wanted to try to obtain more information, so (knowing that ADFS is written in .NET) I knocked together a .NET Service project that just tried to obtain the same certificates private key, and it produces the following exception:

System.Security.Cryptography.CryptographicException: Invalid provider type specified.

   at System.Security.Cryptography.Utils.CreateProvHandle(CspParameters parameters, Boolean randomKeyContainer)
   at System.Security.Cryptography.Utils.GetKeyPairHelper(CspAlgorithmType keyType, CspParameters parameters, Boolean randomKeyContainer, Int32 dwKeySize, SafeProvHandle& safeProvHandle, SafeKeyHandle& safeKeyHandle)
   at System.Security.Cryptography.RSACryptoServiceProvider.GetKeyPair()
   at System.Security.Cryptography.RSACryptoServiceProvider..ctor(Int32 dwKeySize, CspParameters parameters, Boolean useDefaultKeySize)
   at System.Security.Cryptography.X509Certificates.X509Certificate2.get_PrivateKey()
   at WindowsService1.Service1.DoStuff() in c:\Dev\WindowsService1\WindowsService1\Service1.cs:line 45

Which some googling leads me to believe is related to the private keys being stored using CNG, which doesn't work in (pre-4.0 ?) .NET. However, the only advice I've found on correcting this issue is to either a) change the templates on the CA server (I don't personally have any access to this), or b) to export and re-import the certificates – but I've already tried this once.