email certificate on linux with Evolution

Got an email certification. Installed it into Evolution. Evolution very happily signs and encrypts emails using said
certificate. However, none of the recipients are able to validate the signature.

Any suggestions on what needs to be done so that the signature can be validated ?