Como você instalou o Java?
Pacote baixado do site da Sun ou linha de comando (apt-get install)?
se foi a primeira opção, pode ter sido o seguinte: você instalou o Java como o usuário x e somente para o usuário x. Quando o usuário y tenta acessar, não consegue. Tenha certeza que você instalou para todos os usuários (modo convencional do sistema).
Sugiro que instale via linha de comando ou use o Gerenciador de Pacotes.
Não acredito que seja problema de autorização, como estão falando. Afinal, root é superusuário, ou seja, tem permissão pra tudo.
O problema é outro: a variável de ambiente PATH está configurado apenas para seu usuário, não para usuário root. Faça o teste para confirmar, em seu usuário digite:
whereis java
O comando whereis diz onde o binário está localizado, pode ser mostrados vários caminhos separados por ‘:’ (dois-pontos).
Com usuário root, digite um dos caminhos completos que apareceu no whereis. Pode ser algo assim:
/opt/jdk6/java -version
E veja se funciona. Em caso de sucesso, é problema de PATH no root.