O melhor recurso que encontrei neste problema está neste URL. O problema parece ser que temos referências a pacotes hardy em /etc/apt/sources.list, e a solução é apenas removê-los.
Eu só tive o problema dos utilitários sysv, mas apenas removi 4 linhas referindo-se ao hardy do /etc/apt/sources.list corrigido.