A primeira possibilidade que vem à mente é que libjli.so é legível apenas pelo root. Então, um passo:
ls -l $(locate libjli.so)
Se estiver em um local estranho (não em /usr/lib ou /lib ), crie o arquivo /etc/ld.so.conf.d/java.conf contendo o caminho para o diretório que contém libjli.so e execute /sbin/ldconfig como raiz.
Para mais informações sobre solução de problemas, execute este comando, uma vez como raiz e uma vez como usuário não raiz:
ldd java
Em um mundo são, a saída dos dois seria idêntica. O quanto eles diferem deve dizer muito sobre por que isso está falhando.