I have been able to reproduce this issue by installing ca-certificates
(20120212) and ca-certificates-java (20111223) on squeeze and upgrading
to ca-certificates (20120623) and ca-certificates-java (20120721).
Between ca-certificates-java 20111223 and 20120721 the packaging of the
UpdateCertificates class changed from a raw .class file in
/usr/share/ca-certificates-java/ to a jar files. On upgrading
ca-certificates and ca-certificates-java simultaneously the old trigger
of ca-certificates-java is invoked and fails to run the .class file now
replaced with a jar.
The trigger mechanism has been reworked in ca-certificates-java
20121112+nmu1, and upgrading to this version doesn't generate a
NoClassDefFoundError. I also verified that this error doesn't appear
when upgrading from squeeze to wheezy.
This is the maintainer address of Debian's Java team
debian-j...@lists.debian.org for discussions and questions.