Isso é tão estranho. Eu tinha resolvido isso e me deparei com isso mais uma vez. Minha velha sugestão não foi suficiente.
Desta vez eu tive que desinstalar o pip e o pip3 e reinstalá-los. Acho que minha versão pip foi instalada de uma maneira muito estranha usando o easy_install, mas eu poderia desinstalá-lo usando:
sudo pip uninstall pip
Então eu reinstalei o pip:
sudo apt-get install python3-pip