OK, encontrei uma solução que funcionou para mim ...
cd /var/lib/dpkg/info
rm *.postinst
apt-get --force-yes install openjdk-7-jre-headless
Eu apenas assumo que, como o openjdk já estava instalado, isso era apenas um chute, ele não precisa ser openjdk.
Eu então proclamei para limpar o apache e o php
apt-get purge apache2
apt-get purge php
apt-get autoremove
apt-get autoclean
rm -R /etc/apache2 /etc/php
Eu poderia então instalar o apache2 e o php mais uma vez e tudo ficou feliz apt-get instala o apache2 apt-get install php
Que dor de cabeça. dpkg --configure -a
não fez nada e continuou dizendo o erro inicial de dependência, assim como todas as outras soluções que encontrei.