It's actually a problem in nbxmpp, but it seriously affects Gajim. Upstream says it's fixed already, so please backport a patch to 0.4. Reproducible: Always
Thanks fo reporting. I will fix that on monday.
*python-nbxmpp-0.4-r1 (24 Apr 2014) + + 24 Apr 2014; Justin Lecher <jlec@gentoo.org> +python-nbxmpp-0.4-r1.ebuild, + +files/python-nbxmpp-0.4-store-certificate-backport.patch: + Backport patch, #507334 +