Update, I just found a bug that has filed just today, where someone complains about this exact problem with the latest root CA list (version 2.1, as shipped with Firefox 32, NSS 3.16.4), and being unable to connect using gnutls-cli. https://bugzilla.redhat.com/show_bug.cgi?id=1142137 I've added a comment explaining the situation. Kai