Issue
Ubuntu 4.10 seems to have a bug: Even when a proxy is configured at the system level, it is not taken into account by some configuration tools package.
Scenario
When you install the Ubuntu-restricted-extras package, the flashplugin-installer and the ttf-mscorefonts-installer package are also installed. But these last two packages will download files without using the specified proxy.
Result: ubuntu-restricted-extras installation is a failure and you will be unable to install any package in the future (because dpkg will require you to solve the configuration problem in the package before agreeing to install anything).
Solution
Just uninstall the problematic packages:
sudo dpkg -r ttf-mscorefonts-installer sudo dpkg -r flashplugin-installer sudo dpkg --configure -a
The last line to configure the packages installed, will end up with: ubuntu-restricted-extras
If you want to install the Flash plugin or Microsoft fonts, you must do so manually.
Thanks to SebSauvage for this tip.