A new proxy has been set up at my workplace and 'sudo apt-get' always fails. I have set up the proper environment variable but that did not help.

I was just about posting a question to Superuser.com when it striked me that I use 'sudo'. That means it won't be my regular user that runs 'apt-get' therefore all environment variables are lost at the point of execution.

Switched to root, set up environment variable, and issue 'apt-get', and tadaaa, problem solved. It was time to set up the proxy env variable temporarily for root.