I've had identical issue last night. Permissions on private key were set correctly, everything was apparently fine except the Keyset doesn't exist error. In the end it turned out that certificate was imported to the current user store first and then moved to local machine store. However - that didn't move the private key, which was still in the
C:\Documents and settngs\Administrator...
instead of
C:\Documents and settngs\All users...
Altough permissions on the key were set correctly, ASPNET couldn't access it. When we re-imported certificate so that private key is placed in the All users branch, the problem disappeared.