In 6u19, several VeriSign MD2/MD5 root certificates were replaced with stronger SHA1 versions (same key, stronger signature). Some customers using certificates issued from the VeriSign PCA 3 root have been reporting problems that cause their existing certificate chains to be rejected by the JRE because the certificate chain still includes the weaker MD2 root and we disabled MD2 support in 6u17.
The problem is that our certpath validation implementation adds the SHA1 root to the beginning of the chain but does not replace the existing MD2 root. So the chain includes both roots, first the SHA1, then the MD2 and then the rest of the chain. The chain is rejected because the MD2 root is treated as an intermediate CA cert.
It seems our implementation should instead replace the MD2 root with the stronger SHA1 root before validating the chain.