Eu estava recebendo exatamente o mesmo erro.
No Software e amp; Atualizações mudando o servidor do meu país local para o servidor principal, e também adicionando os parceiros Canonical da guia "Outro Software" ajudou a instalar o servidor openssh no meu caso. Não sei qual dos dois ajudou.