Acho que o erro estava na letra "p":
sellassie@sellassie-desktop:~$ sudo update-alternatives --config java
Existem 2 alternativas que provêem`java'.
Escolha de alternativa
-----------------------------------------------
1 /usr/bin/gij-wrapper-4.1
*+ 2 /usr/lib/jvm/java-1.5.0-sun/jre/bin/java
Pressione ENTER para manter o padrão
- , ou digite o número escolhido: 2
Usando `/usr/lib/jvm/java-1.5.0-sun/jre/bin/java' para prover `java'.
sellassie@sellassie-desktop:~$
Como não encontrei o que você indicou escolhi o segundo.