OK, also habe ich gerade versucht, jede Abhängigkeit im Abhängigkeitsbaum zu installieren, und das grundlegende war:
tzdata-java_2012e-0ubuntu0.12.04_all.deb
Ich habe es heruntergeladen von:
https://launchpad.net/ubuntu/+source/tzdata/2012e-0ubuntu0.12.04/+build/3726497/+files/tzdata-java_2012e-0ubuntu0.12.04_all.deb
und getippt:
sudo dpkg -i tzdata-java_2012e-0ubuntu0.12.04_all.deb
Nach nochmal:
sudo apt-get install openjdk-6-jre
Und jetzt geht es in den Installationsprozess.