Problema de dependencia de apt-get Cliente Open-SSH

Esto está en un servidor Ubuntu 12.04.

Recibo este error cuando intento ejecutar alguno apt-get install(intento de instalar paquetes arbitrarios no 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)

Instalar la versión del cliente en cuestión conduce 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

Varios intentos de solucionarlo con falta de conocimientos previos fallaron, por ejemplo

dpkg-reconfigure -a
apt-get -f install

¿Alguien puede dar consejos sobre cómo abordar el problema, posiblemente exigiendo más información necesaria de mi parte?

¿Cómo se puede revertir o quitar la actualización de openssh (que supongo que falló) para poder instalar otros paquetes?

Editar:

Salida de apt-cache policy openssh-clientes:

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

Solo para completar el /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

Simplemente elimine estos paquetes para permitirle usar aptotros paquetes. Ejecute estos comandos en la terminal.

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

Luego reinstale el servidor y el cliente openssh.

sudo apt-get install openssh-server openssh-client

Cuando eliminar / purgar openssh-server y openssh-client no son una opción (por ejemplo, cuando otro paquete depende de ellos)

Esto hizo el truco para mí:

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