The user does not exist or is not unique

One of the web front end servers in our farm was throwing an error when users were being added to a Sharepoint group. The error displayed was the rather generic User does not exist message so I went sniffing in the logs.

Using the Correlation ID I found what was causing the exception,

An exception occurred in AD claim provider when calling 
SPClaimProvider.FillResolveClaim(): Requested registry access 
is not allowed.

A search on this error led me to Bernardo's excellent blog on the problem. I followed his steps and found that my app pool account was indeed being refused access to the registry key

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Shared Tools\
Web Server Extensions\14.0\Secure

I added the App Pool account to the WSS_Restricted_WPG_V4 instead of the local admin group on that server, it worked fine and resolved the issue.