I’ve been fighting with this one for about 2 days…I think the latest trunk version of enigmail, combined with using an LDAP phonebook at work is to blame.

I think I fixed it by setting the key selection to manual in the enigmail configuration, rather than having it try to find the key based upon the recipient email address.