If this happens to you, you are probably changing the password wrong.  You should be doing it using the logon password change prompt or via ctl-alt-delete option while logged into that box.  If you use AD userand and computers (have it reset) or some other out-of-band method this may break certain types of certificates, such as EFS.

If this type of cert does not normally break during a password reset (instead of changed by user directly) then you might check to see if you may be using EFS (maybe you got a little carried away and encrypted the folder that contains the cert).  You can check by running 'cipher /u /n' on their c: drive - it will check all directories automatically.