Esse tipo de quebra de dependência não faz sentido. As versões que a mensagem de erro está reclamando estão disponíveis no Jaunty (por exemplo, versão 0.6c9 do python-setuptools ).
Eu verifico /etc/apt/sources.list
e /etc/apt/sources.list.d/*.list
, e garanta que o mesmo espelho esteja obtendo main, universe e multiverse para atualizações alegres, desenvoltas e inusitadas.