This is a funny problem I encountered on my home computer which runs openSUSE 42.1 Leap. For communication at work, we use Jabber protocol. We migrated to a new server and got it a shiny new Let's Encrypt certificate instead of the self-signed one which was used so far.

My pidgin refused to connect to the Jabber server. Running it in debug mode it showed (also) this:

fiisch@mothership:~> pidgin --debug
...
(17:32:05) gnutls: Starting handshake with someserver.tld
(17:32:05) gnutls: Handshake failed. Error The handshake data size is too large.
(17:32:05) connection: Connection error on 0x56161850ca30 (reason: 5 description: SSL Handshake Failed)
(17:32:05) account: Disconnecting account fiisch@someserver.tld/ (0x561617c35b90)
(17:32:05) connection: Disconnecting connection 0x56161850ca30
(17:32:05) connection: Destroying connection 0x56161850ca30
...

Pidgin has a long history for SSL-related issues which generally seem to boil down to using gnutls. The application supports also NSS, though. The log showed that NSS was properly loaded.

Possible problem I encountered is this: http://savannah.gnu.org/support/?106396. The main point is that GnuTLS seem to be using some fixed buffer for certificates which it then tries to validate.