ОК, поэтому я просто попытался установить все зависимости в дереве зависимостей, и самое основное было:
tzdata-java_2012e-0ubuntu0.12.04_all.deb
Я скачал это с:
https://launchpad.net/ubuntu/+source/tzdata/2012e-0ubuntu0.12.04/+build/3726497/+files/tzdata-java_2012e-0ubuntu0.12.04_all.deb
и набрал:
sudo dpkg -i tzdata-java_2012e-0ubuntu0.12.04_all.deb
После снова:
sudo apt-get install openjdk-6-jre
И теперь это в процессе установки.