Qualys does not appear to have an issue [1]. Testssh.sh [2] complains that they offer DES/IDEA and may also be vulnerable to CVE-2013-3587 but otherwise also gives them an A+.

Have you tried multiple browsers and is your OS CA store up to date?

[1] - https://www.ssllabs.com/ssltest/analyze.html?d=www.gov.uk

[2] - https://github.com/drwetter/testssl.sh

Attackers might be trying to steal your information from www.gov.uk (for example, passwords, messages or credit cards). Learn more NET::ERR_CERT_AUTHORITY_INVALID

I'm not getting that at all from your link.