Teoreticky by mohl být problém v tom, že chybí nějaké závislosti, které třeba přibyly k nové verzi. Zkus ty balíky reinstalovat, tím by si závislosti doplnily
sudo apt-get install --reinstall openjdk-6-jre openjdk-6-jre-headless openjdk-6-jre-libpak zkus znovu
sudo apt-get update && sudo apt-get upgradea uvidíš.