Comment # 3 on bug 939743 from Vitezslav Cizek

From the log it looks like pidgin is using NSS, not openssl.

In recent months there were updates to most ssl implementations which caused
problems with some servers.
To fix a logjam vulnerability (CVE-2015-4000, bug 931600), only Diffie-Hellman
groups stronger than 768 (or somewhere 1024) bits are now allowed.

So maybe the server you're connecting to is using these short parameters.
You can check it by using:
gnutls-cli HOST -p PORT --priority=PFS:+DHE-RSA:-ECDHE-RSA -d 255