Verificando as dependências reversas nos outros pacotes revela a causa:
$ apt-cache show python-nose | grep Depends
Depends: python-pkg-resources, python2.7, python (>= 2.6.6-7~), python (<< 2.8), python2.6
Já existe um bug relatado sobre o problema.