Você pode querer experimentar o cliente Java oficial da Sun (Oracle), em vez do OpenJDK. Para fazer isso, execute synaptic em System / Administration / Synaptic, depois clique em Settings / Repositories, então escolha a guia" Outro Software ". Agora coloque um carrapato ao lado de "Canonical Partners" e tudo bem e recarregue seus pacotes.
Agora, pesquise por "JRE". Remova os pacotes "openjdk" e selecione os pacotes "sun-java6". Quando você clicar em aplicar, você será informado de que removerá "default-jre", mas não se preocupe com isso, pois já adicionou manualmente o que deseja.
Dê ao seu pacote outra chance e veja se ele tem um desempenho diferente.