Server 2008: Keyset does not exist when installing scheduled task

The product I work on has an installer that does a whole bunch of things, including installing regular files, setting registry keys, installing websites and web services on IIS and creating scheduled tasks. We have used this installer for years and now and then we have an issue with it but we can usually get it sorted. This one has us stumped.

We are trying to create a bunch of scheduled tasks, and every time it is coming back saying "Keyset does not exist (Exception from HRESULT: 0x80090016)". We have used this installer on several different machines today and had no issues, but we are having issues with one in particular.

Every google search has told us it is an issue with the Protected Storage service. At first we found this service was not running, so we started it and we are still having trouble. Other searches have suggested clearing out a folder in Documents and Settings\All Users\Application Data\Microsoft\Crypto, but given that we are running on Server 2008 that path doesn't exactly exist and I have not managed to find where it might be instead (I've looked in the Users folder under Default, figuring that's the user that replaced "All Users").

I've also seen some results appearing for when you are dealing with IIS on server 2008 and those suggest there is an issue with some certificates not allowing access to the IIS user, but we don't use certificates in our install and the error is happening before we hit IIS.

For those that know code, we use TaskScheduler.dll (which as far as I understand handles all the COM+ stuff for you) to create our tasks, and our installer is built using the WiX toolkit and C#.

Has anyone ever seen an issue like this or seen this error and managed to fix it or get around it?

We found that we had to delete/rename the S-1-5-18 folder in C:\ProgramData\Microsoft\Crypto\RSA. Once that was done we had no issues.