problema de dependência do apt-get Cliente Open-SSH

Este é um servidor Ubuntu 12.04.

Estou recebendo esse erro ao tentar executar qualquer um apt-get install(tentando instalar pacotes arbitrários não relacionados):

dpkg: dependency problems prevent configuration of openssh-server:
 openssh-server depends on openssh-client (= 1:5.9p1-5ubuntu1.1); however:
  Version of openssh-client on system is 1:5.9p1-5ubuntu1.4.
dpkg: error processing openssh-server (--configure):
 dependency problems - leaving unconfigured
No apport report written because the error message indicates its a followup error from a previous failure.
                                                                                                          dpkg: dependency probms prevent configuration of ssh:
 ssh depends on openssh-server; however:
  Package openssh-server is not configured yet.
dpkg: error processing ssh (--configure):
 dependency problems - leaving unconfigured
No apport report written because the error message indicates its a followup error from a previous failure.
                                                                                                          Errors were encounter while processing:
 openssh-server
 ssh
E: Sub-process /usr/bin/dpkg returned an error code (1)

A instalação da versão do cliente em questão leva a:

sudo apt-get install openssh-client=1:5.9p1-5ubuntu1.1
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: Version '1:5.9p1-5ubuntu1.1' for 'openssh-client' was not found

Várias tentativas para corrigi-lo com falta de conhecimento prévio falharam, por exemplo,

dpkg-reconfigure -a
apt-get -f install

Alguém pode dar conselhos sobre como resolver o problema, possivelmente exigindo mais informações necessárias do meu lado?

Como a atualização do openssh (que eu acho que falhou) pode ser revertida ou retirada de foco, para que eu possa instalar outros pacotes?

Editar:

Saída de apt-cache policy openssh-clientis:

openssh-client:
  Installed: 1:5.9p1-5ubuntu1.4
  Candidate: 1:5.9p1-5ubuntu1.4
  Version table:
 *** 1:5.9p1-5ubuntu1.4 0
        500 http://archive.ubuntu.com/ubuntu/ precise-updates/main amd64 Packages
        100 /var/lib/dpkg/status
     1:5.9p1-5ubuntu1.3 0
        500 http://security.ubuntu.com/ubuntu/ precise-security/main amd64 Packages
     1:5.9p1-5ubuntu1 0
        500 http://archive.ubuntu.com/ubuntu/ precise/main amd64 Packages

Apenas para completar, o /etc/apt/sources.list:

deb http://archive.ubuntu.com/ubuntu precise main restricted universe multiverse
deb http://archive.ubuntu.com/ubuntu precise-updates main restricted universe multiverse
deb http://archive.ubuntu.com/ubuntu precise-backports main restricted universe multiverse
deb http://security.ubuntu.com/ubuntu precise-security main restricted universe multiverse

Apenas remova esses pacotes para permitir que você use aptoutros pacotes. Execute estes comandos no terminal.

sudo apt-get remove openssh-server openssh-client --purge && sudo apt-get autoremove && sudo apt-get autoclean && sudo apt-get update

Em seguida, reinstale o servidor e o cliente openssh.

sudo apt-get install openssh-server openssh-client

Ao remover / limpar o openssh-server e o openssh-client não são uma opção (por exemplo, quando outro pacote depende deles)

Isso fez o truque para mim:

sudo dpkg -i /var/cache/apt/archives/openssh-*.deb
sudo dpkg --configure -a