NTLM proxies are relatively common corporate web proxy. It takes special software to pass through it, unfortunately. One must essentially log into an NT domain to get to the web past the proxy. By default, web browsers are the only software on Ubuntu Linux that know how to perform the complex handshake. Many core tools (like apt, etc) cannot do what they need — and your system can’t download software updates.
One solution: ntlmaps — NTLM Authorization Proxy Server. Roughly following the guide here, it’s pretty quick to get done. You will want to replace the URL in “Step 1” with a recent one, such as (for 9.10) http://packages.ubuntu.com/karmic/all/ntlmaps/download.
The beauty of this is that, since Firefox can get past the NTLM proxy, you can download the ntlmaps package directly and install it. After it is set up, reconfigure System > Preferences > Network Proxy to localhost:5865, restart all apps (including terminals), and everything should be ready to go.
The one concern I have is that it stores my password in plain text at /etc/ntlmaps/server.cfg — granted, you must have sudo access to read it. You can apparently have it prompt when it starts up, but I’m not sure how this impacts the UI.
From reading the config file, it appears you can at least use the browser to store the password, in the basic auth scheme. It is possible you could even use the system preferences to do so, which is at least a bit more user-friendly. You will still have to remember to change the password, though.
Note: While ntlmaps works pretty well for apt and the update manager, it has pretty poor performance for general browsing use. Cntlm was written to address the speed side of things, but I haven’t tried it yet. See http://cntlm.sourceforge.net/