Consegui resolvê-lo. Primeiro eu tive que baixar todos os pacotes no link que mencionei equipe proposta do Ubuntu Secure
Eu fiz isso usando os seguintes comandos:
sudo wget https://launchpad.net/~ubuntu-security-proposed/+archive/ubuntu/ppa/+build/5935007/+files/openjdk-7-jre_7u55-2.4.7-1ubuntu1~0.12.04.2_amd64.deb
sudo wget https://launchpad.net/~ubuntu-security-proposed/+archive/ubuntu/ppa/+build/5935007/+files/openjdk-7-jre-zero_7u55-2.4.7-1ubuntu1~0.12.04.2_amd64.deb
sudo wget https://launchpad.net/~ubuntu-security-proposed/+archive/ubuntu/ppa/+build/5935007/+files/openjdk-7-jre-headless_7u55-2.4.7-1ubuntu1~0.12.04.2_amd64.deb
sudo wget https://launchpad.net/~ubuntu-security-proposed/+archive/ubuntu/ppa/+build/5935007/+files/openjdk-7-jdk_7u55-2.4.7-1ubuntu1~0.12.04.2_amd64.deb
Então tentei instalar tudo manualmente, nesta ordem:
sudo dpkg -i openjdk-7-jre-zero_7u55-2.4.7-1ubuntu1~0.12.04.2_amd64.deb
sudo dpkg -i openjdk-7-jre-headless_7u55-2.4.7-1ubuntu1~0.12.04.2_amd64.deb
sudo dpkg -i openjdk-7-jre_7u55-2.4.7-1ubuntu1~0.12.04.2_amd64.deb
sudo dpkg -i openjdk-7-jdk_7u55-2.4.7-1ubuntu1~0.12.04.2_amd64.deb
Todos os comandos acima resultarão em erros de dependências, apenas ignorei todos e executei o seguinte comando:
sudo apt-get -f install
Tudo foi instalado e está funcionando bem. Parece que o comando apt-get -f install
tenta resolver erros de dependências anteriores instalando todas as dependências necessárias (não tenho certeza, pois não sou especialista).
Se alguém achar que esse não é o procedimento correto, avise-nos.