we had faced this access denied issue when we tried to renew Exchagne 2007 certificate. The error was showing below
I login as Administrator and i am sure i have all the access in Domain and Exchange
After searching we have found that the solution.
On the “C:\Documents and Settings\All Users\Application Data\Microsoft\Crypto\RSA folder” folder go ahead and right click, properties, security.
Now for the exchange administrators I’m sure you already will see full permissions, but go ahead and click advanced, under permissions for the administrators first make sure it says “‘this folder, subfolders and files” and not “‘this folder only” and finally go ahead and check the box at the bottom that says replace permissions on all child objects just to make sure the sub folders are currently set properly.
Ahh. After this i am able to renew the certificate. Please see the below screen shot
Exchangegeek from msexchangegeek.com has a great post on how to renew the Exchange 2007 certificate here