@Stanislav: are you per chance using a cacert.org-certificate? The problem seems to have to do with a self-signed root certificate that uses MD5 (as the root cert from cacert.org does) for its signature.
If the server provides such a root certificate in the certificate chain, gnutls will refuse to connect, even if the root cert is known to - and trusted by - the client.
