The above error was reported by a customer from his Access Proxy. The first thought was locked down permissions on the server to the certificate store but that was not the case.
For this customer issue they were using a domain service account instead of the local service account. Specifically - the Access Proxy was running with LCService from the domain, changing this to the local LCservice (normally this is LCProxyService) and restarting the service the error went away.
This would not be a normal config for most customers but it wasn't documented anywhere until now.
Credit for this goes to Devank