What key mode are you using, or what key modes are allowed?
Are you using silent enrollment?
Errors like this are usually seen when a GKM key is allowed, and silent enrollment is used. Every time the user logs on to a new system he will be prompted for the key passphrase. If using Silent Enrollment, we recommend using SKM mode only. Otherwise, a GKM key will be created, using their current Windows passphrase when they first enroll, but the passphrase on that key will not change, so after several Windows passphrase changes, the user will likely not remember the GKM key passphrase.
Are you using consumer matching for grouping users automatically? If so, is this user maybe getting matched incorrectly, or getting matched to a different group than expected?