Last weekend I came across a problem to which I could not find a solution on Google.
The ldaps certificate on one of our AD LDS (ADAM) servers had expired. As we've had problems changing AD LDS certificates before I knew it could be tricky.
But after following all available instructions (for example https://www.dirwiz.com/kb/345 which explains how the private keys in C:\Documents and Settings\All Users\Application Data\Microsoft\Crypto\RSA\MachineKeys must have the correct permissions set for the AD LDS service to read the private key for the certificate we still could not get it working.
Finally I found a/the solution by chance:
First backup the registry key HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Cryptography\Services\ADAM_Lund01\SystemCertificates\My\Certificates
Then delete all keys there EXCEPT for the key matching the SHA1/Thumbprint of your new certificate.
Restart the AD LDS service and you're good to go.
If your new certificate is from a different CA than your old certificate you will most likely have to reboot your server and not just the service.