Recentemente, tive o mesmo problema - a maneira como consertei isso foi desinstalar o OpenJDK 7 e instalar o OpenJDK 6 .
Eu não tenho idéia do motivo pelo qual o OpenJDK 7 não quer funcionar, mas ele começou a falhar quando eu o instalei através do Terminal.
Instalar o OpenJDK 6 é como instalar uma nova versão do Java.
Eu tentei muitos outros comandos diferentes e eles não funcionaram.