Hmmm. By way of an experiment, could you try getting another key pair to see if that works - you can get a free one at
www.cacert.org. I know you probably need to use the one particular key pair you have a problem with, but it may give some clue.
What other email clients did you try. Different Linux distributions are unlikely to be different (it's more likely to be an application problem).
Just to be absolutely clear, you did add trust to the
CA certificate, not (just) your own certificate, right?
I think it's true that X.509 certificates can carry permissions about what they're allowed to be used for (authentication, signing, encryption). Do you know that the certificate is allowed to be used for signing? If not, it will never work (though the error message is very inappropriate, if that's the case!).
Cheers,
-nick