Eu novamente limparia o python-pip e o instalaria de forma diferente
wget https://bootstrap.pypa.io/get-pip.py
Então
sudo python get-pip.py
E veja se isso funciona melhor para você.
editar
Este trajeto leva você a uma novidade em relação ao repo. Você também pode atualizar usando
pip install -U pip
Não tenho certeza se você pode fazer isso se for instalado com o apt-get.