First of all, thank you very much for taking the time to post, I really do appreciate it ! :-)
Would you be entirely sure that the e-mail address used on the certificate is the address of the account you are trying to use to send a signed mail, you may want to make sure that you have both keys and the CA certificate in your keychain. Indeed, would you only have one of the pieces, Mail won't be able to use them.
Also, you may want to use the "Keychain First Aid" utility, built into the "Keychain Access" utility to make sure that your keychain is not damaged.
Let me know if this helps !