Поиск библиотеки в программном центре

Похоже, у вас сломанная установка на Java.

Попробуйте sudo apt-get purge openjdk-jre.

Тогда я бы порекомендовал пометить хранилище «Партнеры» в синаптическом режиме, перезагрузить и установить Sun JRE с sudo apt-get install sun-java6-jre.