Didn't work for me, though I had the same error.  Had an Event ID of 6482 and plenty of "System.Security.Cryptography.CryptographicException: The handle is invalid." kind of messages in the logs.  I would have thought your fix would've done it, but apparently there's a little bit more to my issues than yours.  Even an IISRESET after changing the ACL didn't work to let me start the service.

Even after adding the Network Service, (Local) Administrators, and Everyone groups to the blasted folder at the "Full Control" level, and doing an IISRESET afterwards, it still would not work for me.  I had to go Napoleon on it and apply that not just to the folder, but make all the contents inherit the bloody permissions.

In the Security tab of the folder's Properties:

Click Advanced

Click the Owner tab

Ensure the current owner says Administrators, if not, click it in the "Change owner to" box

Check the checkbox that says "Replace owner on subcontainers and objects"

Hit Apply

Click the Permissions tab

Add the Everyone group (if you haven't already) by using the Add button, type Everyone, and click OK

Highlight the Everyone group and click Edit

Ensure "Allow" is checked for all the boxes and click OK

Check the box that says "Replace permission entries on all child objects with entries shown here that apply to child objects"

Click Apply, then Yes on the warning to continue

Click OK

Then click Apply & OK on the MachineKeys Properties window.

This all did the trick for me.  :-)

-Tom