説明不足だったカモだけど, 設定の確認をしているだけで動作は変わりません。
一つ目は環境変数 JAVA_HOMEとか, 二つ目は他に Java環境が入っていないかどーか … です。


んで, あとは, もっと細かく設定を調べていくとか,
aptitude/apt-get で purgeで削除してみて Java再インストールしてみるとか,
そのときに libjavaplugin.so や firefox-javaplugin.so がどーなったかとか,
(Appletじゃなく) Javaなプログラムを作成して動かしてみるとどーなるかとか,

… いくつか確認しながら調べることできるかもだけど, Javaの reinstallでもダメなら, 手っ取り早いのは Ubuntuごと再インストールかもです (まだクリーン状態に近ければ)。
(もちろん上の項目を試してみるのもアリだけど)