Is the console output or backtrace any different with KMail 3.5.9? Also, did you upgrade "kleopatra" and "libkleopatra1" to 4:3.5.9-2? They're responsible for much of the crypto-related functionality in KMail.
Attachment:
signature.asc
Description: This is a digitally signed message part.