Comment 9 for bug 122325

I "solved" the problem by copying the file /usr/lib/jvm/java-6-sun-1.6.0.03/jre/lib/jexec to /var/lib/binfmts/jexec and after that I ran sudo dpkg --purge remove sun-java6-bin sun-java6-jre

Not to nice, it complained a lot and then it worked. Probably not recommended.