Quando não se usa proxy transparente, você é obrigado a configurar manualmente cada servidor/estação de trabalho para poder utilizar o APT e baixar/instalar seus pacotes pelo nosso tão conhecido apt-get ou aptitude. No Ubuntu configuramos da seguinte maneira:

Edite/crie o arquivo /etc/apt/apt.conf.d/02.proxy

# touch /etc/apt/apt.conf.d/02proxy

# nano -w /etc/apt/apt.conf.d/02proxy

Insira o seguinte script, caso o proxy não exija autenticação:

Acquire {
HTTP::proxy "http://servidor-proxy:porta";
FTP::proxy "http://servidor-proxy:porta";
}

Se o proxy exige autenticação:

Acquire {
HTTP::proxy "http://usuario:senha@servidor-proxy:porta";
FTP::proxy "http://usuario:senha@servidor-proxy:porta";
}

Não esqueça que, para evitar que outros usuários leiam o arquivo, configure a permissão 600