I have just received the following update from IBM:
This was an intentional change by the JVM team in Java6SR16FP20 to tighten security by disabling the MD5 algorithm by default in last JVM release. Unfortunately the Domino server console can only do MD5 right now. Workaround is to re-enabled the MD5 algorithm in JVM
Navigate to this file. The values in blue were pointed out, so removing them should remedy.
jre/lib/security/java.security
jdk.certpath.disabledAlgorithms=MD2, MD5, RSA keySize < 1024
jdk.tls.disabledAlgorithms=SSLv3, RC4, MD5withRSA, DH keySize < 768
It is a shame they could not have documented this beforehand!!!
Hopefully this will be resolved in FP6