É um problema com sudo . Se você usa sudo , a variável $http_proxy é desconhecida neste contexto.
sudo -i abre um shell de raiz. Lá você pode definir a variável $http_proxy novamente e depois easy_install funciona - você não precisa usar o sudo porque você já é superusuário.
$ sudo -i
# export http_proxy=http://192.168.1.25:80
# easy_install virtualenv
Ou você pode ter seu ambiente real no contexto sudo e salvar a "etapa raiz":
$ sudo -E easy_install virtualenv