Tive um problema semelhante há um tempo atrás. Se bem me lembro, foi resolvido limpando e reinstalando com
sudo apt-get purge python-pip
seguido por
sudo apt-get update
sudo apt-get install python-pip
A limpeza remove os arquivos de configuração, bem como a desinstalação do pacote.