Eu tentei de maneira mais simples do que no comentário da pergunta, e parece que funciona para mim.
Eu baixei o arquivo .deb para openjdk-7-jre-headless:
wget http://mirror.pnl.gov/ubuntu/pool/universe/o/openjdk-7/openjdk-7-jre-headless_7u21-2.3.9-0ubuntu0.12.04.1_i386.deb
Então eu tentei:
dpkg -i openjdk-7-jre-headless_7u21-2.3.9-0ubuntu0.12.04.1_i386.deb
E recebi uma mensagem dizendo sobre a versão incompatível do openjdk-7-jre-lib (esqueci de copiar a mensagem em si, desculpe)
Eu baixei o arquivo .deb para o openjdk-7-jre-lib:
wget http://mirror.pnl.gov/ubuntu/pool/universe/o/openjdk-7/openjdk-7-jre-lib_7u21-2.3.9-0ubuntu0.12.04.1_all.deb
Então eu tentei:
dpkg -i openjdk-7-jre-headless_7u21-2.3.9-0ubuntu0.12.04.1_i386.deb openjdk-7-jre-lib_7u21-2.3.9-0ubuntu0.12.04.1_all.deb
E pareceu degradar corretamente.