After installing the various gpg-agent packages (gpgsm, gpgagent etc.) and still no luck a simple “sudo apt-get install pinentry-qt” did the trick (installs the password-entry dialog). Note that you have to start the gpg-agent manually (eval `gpg-agent –daemon`) before starting KMail.