I have just installed Linux Mint Maya using linuxmint-13-mate-dvd-32bit.iso file
I installed it in a computer connected to a network behind a proxy but did not add proxy info during installation.
After instalation, I added proxy info in the config application. This successfully recorded the proxy info, and when I wrote $http_proxy or $ftp_proxy on the command terminal I could see the correct proxy address. However, with the proxy correctly configured, apt-get did not work, being unable to connect to any server.
However, after that, and searching for information in the web, I solved the problem creating the file /etc/apt/conf.d./30proxy and adding there the proxy info:
Where "IP" is the IP of the proxy. After this, I could sucessfully update my system.
It seems that apt-get searches for proxy information in two different places, or makes in some cases mistakes acquiring the proxy information.