Determine whether the Network Service account has the correct permissions. Make sure that the Network Service account has Read permissions on all the keys in the following directory: C:\Documents and Settings\All Users\Application Data\Microsoft\Crypto\RSA\MachineKeys, where C:\ is the directory to which Exchange 2007 was installed.
After you run new-ExchangeCertificate, run the command Get-Exchangecertificate (to find out the thumbprint of the cert you added) and then the command Enable-ExchangeCertificate -Thumbprint <your data> -Services SMTP.
Filemon can also be used to determine whether this is a permissions problem.
After struggling with a server that popped up this message for 2 hours, I finally sorted out the problem. The 1037 error came because the server had a CA installed and a CA cert was installed into Exchange (not sure if this happened automatically). The "S" in the Get-ExchangeCertificate was not visible and no matter how much I tried Enable-ExchangeCertificate it did not help.
To resolve the problem make sure that the Network Service account has Read permissions on the key (look for the thumbprint) in the following directory: C:\Documents and Settings\All Users\Application Data\Microsoft\Crypto\RSA\MachineKeys, where C:\ is the root in which Exchange 2007 was installed. You need to set this permission on the individual file, not on the folder. Article “How to Troubleshoot Direct Trust Certificate Errors 1037 and 2019” helped me to resolve the problem.
This problem can have multiple causes. See ME935629
for information on solving it.