The site's security certificate is signed using a weak signature algorithm!
[snip]
I originally created the certificates using the instructions in the Apache SSL FAQ. It turns out that this results in SSL certificates that use the weaker MD5 signature hash algorithm which is the cause of the complaint. This is easily fixed by adding '-sha1' to the openssl command line when generating the certificate. Like so:
$ openssl req -new -x509 -sha1 -nodes -out server.crt -keyout server.key