Похоже, что-то напортачило во время обновления pip.
Я обошел проблему, переустановив pip с помощью easy_install:
easy_install pip
И затем связавшись с этой версией:
ln -sv /usr/local/bin/pip-2.6 /usr/bin/pip
(РЕДАКТИРОВАТЬ)
Вот полная последовательность с нуля:
apt-get install python-pip python-dev build-essential
pip install pip --upgrade
pip install virtualenv
Здесь произошла ошибка импорта,Чтобы восстановить, выполните следующие действия:
easy_install pip
rm /usr/bin/pip
ln -sv /usr/local/bin/pip-2.6 /usr/bin/pip
pip install pip --upgrade
pip install virtualenv
Возможно, этого можно избежать, просто используя easy_install с самого начала, но в данный момент у меня нет чистой установки Debian, чтобы подтвердить это.