Isso acontece porque o PATH é diferente ao ser executado com sudo . Tente comparar:
which pip
env
vs.
sudo which pip
sudo env
Uma solução segura é criar um link simbólico para pip em /usr/local/bin ou mesmo /usr/bin . Se você instalar o pip usando um gerenciador de pacotes, ele fará isso automaticamente em várias distros (a maioria?).