O problema existe em várias versões do Ubuntu (16.04, 16.10 por certo), bem como o seu.
Mesmo um pip list -o
básico falha (isso confirma a condição).
Vale a pena notar que os módulos python e self-install do SO podem ser problemáticos, por isso, prossiga ao seu próprio "risco".
Remover o atual pip :
sudo su -
pip uninstall pip
Obtenha o pip instalador:
wget https://bootstrap.pypa.io/get-pip.py
(Re) Instale o pip :
python get-pip.py
Atualize todos os ovos:
for i in 'pip list -o --format legacy|awk '{print $1}'' ; do pip install --upgrade $i; done