Zkus zrestartovat po úpravě počítač. Funguje mi to v obdobné firemní síti, pro kterou je rovněž autorizace vyžadována (záleží samozřejmě na správci sítě jak nastaví, které služby jsou přes proxy autorizovány), přesto pro tebou popisované případy to běhá. Alespoň v příkazové řádce přes terminál by mělo. Jak je to s Gnome nevím, nepoužívám ho. KDE se po výše uvedené úpravě začalo normálně připojovat. Kdyby to přes to nechodilo, zkus ještě doplnit přihlašovací jméno a heslo na proxy podle následujícího vzoru http://mojedoména\jméno:heslo@proxy.firma.cz:port