Usually when you see a cert box it is either a problem with the web server being configured to require client authentication certificates - but other users don't need to select one. If this doesn't happen to all users, such as in your case, then it is usually an issue with the browser - yet this is happening in IE and FF. Since does not occur for same user elsewhere it isn't some weird user specific thing, and since other users don't experience it on the same box it isn't just the box.
It is possible that maybe the rest of the clients do actually have a similar Verisign cert and it works fine. Assuming not, I'm thinking that a corrupt Windows profile is to blame. Try creating a new profile and import the Verisign cert with private key.
Another possibility is that the way the user is logging in just doesn't match the subject name of the cert. Try looking on the details tab of the cert for Subject and Subject Alternate Name and see what username formats are in place - maybe you need to log in as
[email protected] instead of having the username on a different line and taking the domain from the dropdown, or using domain\username. I'm assuming their AD information didn't change - like a name change due to marriage or anything like that where the cert may be trying to check something else that used to match but no longer does?
Right now my bet's on the profile, but dig into it a little bit.