O seu proxy requer autenticação? Se sim, então seu arquivo apt.conf deve se parecer com isto
Acquire::http::Proxy "http://username:password@server:port";
Acquire::https::Proxy "https://username:password@server:port";
Acquire::ftp::Proxy "ftp://username:password@server:port";
Acquire::socks::Proxy "socks://username:password@server:port";
Nota: O Mozilla Firefox funciona bem porque acessa o proxy da configuração de rede e solicita autenticação quando você abre o firefox.