Ah, eu encontrei o problema.
O Update Manager (que é, na verdade, o KPackageKit) usará o proxy configurado em .kde/share/config/kioslaverc
. Mas, no KUbuntu 9.10, essa configuração de proxy não é exibida nas configurações ... Elas não são exibidas no Konqueror ou nas Configurações de Rede ... Portanto, não havia como encontrar esse problema.
Graças a essa postagem para obter informações sobre essas configurações de proxy.