git clone using HTTPS fails with "gnutls_handshake() failed"

gitlab-rake.logI have setup a gitlab CE 8.5.1 server (running on CentOS 7). Because we're evaluating, for now it has a self-signed certificate. Cloning using git@ works fine but, when using https, I get a fatal error.

git -c http.sslVerify=false clone https://user:password@gitlab.company.com/GRP/REPO.git/

Running that from an up-to-date Ubuntu Desktop 14.04 system, results in:

fatal: unable to access 'https://user:password@gitlab.company.com/GRP/REPO.git/': gnutls_handshake() failed: The signature algorithm is not supported.

From a Windows 7 system the same command results in: fatal: Authentication failed for 'https://user:password@gitlab.company.com/GRP/REPO.git/'

I realize this is not the best way to clone, but the method works fine when using GitHub enterprise.