Este foi um problema de repositórios conflitantes. Eu tinha alguns repositórios apontando para o Ubunto 12.04 (Precise). Com base nesta resposta link
Uma vez eu os removi e corri
sudo apt-get update
sudo apt-get -f install
Funcionou bem
Get:1 http://in.archive.ubuntu.com/ubuntu xenial/main amd64 python-setuptools all 20.7.0-1 [169 kB]
Fetched 169 kB in 3s (47.0 kB/s)
(Reading database ... 348605 files and directories currently installed.)
Preparing to unpack .../python-setuptools_20.7.0-1_all.deb ...
Unpacking python-setuptools (20.7.0-1) ...
Setting up python-setuptools (20.7.0-1) ...
Setting up python-cryptography (1.6) ...
Setting up python-zope.interface (4.3.2) ...
A instalação da cassandra depois disso também funcionou bem quando a dependência foi classificada.
Esta é a política do apt-cache após a instalação bem-sucedida
sudo apt-cache policy python-setuptools python-pkg-resources
python-setuptools:
Installed: 20.7.0-1
Candidate: 20.7.0-1
Version table:
*** 20.7.0-1 500
500 http://in.archive.ubuntu.com/ubuntu xenial/main amd64 Packages
500 http://in.archive.ubuntu.com/ubuntu xenial/main i386 Packages
100 /var/lib/dpkg/status
python-pkg-resources:
Installed: 20.7.0-1
Candidate: 20.7.0-1
Version table:
*** 20.7.0-1 500
500 http://in.archive.ubuntu.com/ubuntu xenial/main amd64 Packages
500 http://in.archive.ubuntu.com/ubuntu xenial/main i386 Packages
100 /var/lib/dpkg/status