Seems to me that the xlibs should be a dependency of java-package. This is necessary for dpkg-shlibdeps to properly create the dependencies of the VM. Probably the AWT stuff.