Exchange & Certificate Issue ( Digital ID name cannot be found by underlying security )

Our network consist of roughly 400 workstations and our mail system is Exchange 2003.  We use the Microsoft certificates which are deployed using AD for Digital ID's and Encryption.

Our issue is that several people receive encrypted or digital signed emails and when they try to open the email they receive the following message:

"Your digital ID name cannot be found by the underlying security system"

I've checked the users Certificates and they have the ones from AD and I'm stumped so any help would be greatly appreciated.