Apenas no caso de alguém mais se deparar com um problema semelhante:
Uma opção é usar o dpkg e, quando necessário, forçar a instalação / configuração de certos pacotes. Cheguei a esta questão por causa da menção de openssh-server, que no meu caso estava preso.
% bl0ck_qu0te%Estava preso porque o openssh-client já estava atualizado (de alguma forma) para o 1.4. Consegui resolver isso forçando a configuração do servidor openssh usando
% bl0ck_qu0te%que instalou o openssh-server, que então me permitiu atualizar o openssh-server para uma versão mais nova correspondente à versão openssh-client instalada.