O problema parece ter sido que eu instalei manualmente o Python em uma versão mais recente do que a distribuição fornece. Quando o apt-get tenta reparar a instalação, ele precisa fazer downgrade, o que só é possível se você especificar que deveria.
Criando um arquivo /etc/apt/preferences.d/allow-downgrade
contendo
Package: *
Pin: release o=Ubuntu
Pin-Priority: 1001
e depois executando
apt-get update
apt-get upgrade
apt-get -f install
apt-get update
resolveu o problema.
Para uma fonte e uma resposta mais detalhada:
link