It is very likely that you have an old or incorrect key for the contact. To fix this, delete the contact AND the saved certificate from your email client and then create the contact again. The new key will then be saved and sending encrypted e-mails will work.