Итак, проблема была в том, что мне нужно было бежать:
sudo apt-get update
Затем выполните команду:
sudo apt-get install sun-java6-jre
работает! Но вам будет предложено принять пользовательское соглашение. Я использую Windows и Putty, и было не совсем понятно, как принять это (нажатие OK не работает). Мне пришлось нажимать на вкладку, пока она не была выделена.
Наконец-то это сработало.