Eu apenas executei os mesmos comandos que você e não produzi o mesmo erro.
$ sudo easy_install requests
Searching for requests
Reading http://pypi.python.org/simple/requests/
Best match: requests 2.0.0
Downloading https://pypi.python.org/packages/source/r/requests/requests-2.0.0.tar.gz#md5=856fc825c17483e25fd55db115028e3f
Processing requests-2.0.0.tar.gz
Writing /tmp/easy_install-8vDXEw/requests-2.0.0/setup.cfg
Running requests-2.0.0/setup.py -q bdist_egg --dist-dir /tmp/easy_install-8vDXEw/requests-2.0.0/egg-dist-tmp-HTUm16
Adding requests 2.0.0 to easy-install.pth file
Installed /usr/local/lib/python2.7/dist-packages/requests-2.0.0-py2.7.egg
Processing dependencies for requests
Finished processing dependencies for requests
$ pip install requests
Requirement already satisfied (use --upgrade to upgrade): requests in /usr/local/lib/python2.7/dist-packages/requests-2.0.0-py2.7.egg
Cleaning up...
Vou ter que verificar o que o log diz, mas como você vê o pip funciona muito bem. Você pode precisar reinstalar o pip:
sudo apt-get --purge autoremove pip
sudo apt-get install pip