The credential selected for signing is invalid

We have a Windows network of about 200 users, may of whom have Adobe Acrobat or Reader running on their Windows workstation or laptops. Our setup has a self-signed certificate managed by the Windows Servers. Our root certificate was changed a year ago because of some server problemm, but on the whole, signing PDF documents with digital signatures continues to work well. Lately, some users have been getting "the credential selected for signing is invalid"  during the last step of making a digital signature in Reader or Acrobat.

Some old posts regarding this issue concerned a MAC system, which does not apply here. Another post said the solution was to chuck out the certificates - I presume from some cache in the workstations, there were no specifics on that. So, what are the main reasons for this message and how is the problem fixed?