Ok, depois de algumas pesquisas, decidi fazer o seguinte:
rm /usr/local/lib/python2.7/dist-packages/setuptools-20.7.0-py2.7.egg
sudo apt-get purge python-pip
wget https://bootstrap.pypa.io/get-pip.py
python get-pip.py
Agora o pip funciona sem problemas.