apt-cache show mostra as seguintes dependências: gstreamer0.10-plugins-ugly-multiverse, ttf-mscorefonts-installer, unrar, gstreamer0.10-plugins-bad-multiverso, libavcodec-extra-52, libmp4v2-0
Removendo o ttf-mscorefonts-installer e adicionando a dependência de addons restritos do Ubuntu, nós criamos isto:
sudo apt-get install gstreamer0.10-plugins-ugly-multiverse unrar gstreamer0.10-plugins-bad-multiverse libavcodec-extra-52 libmp4v2-0 ubuntu-restricted-addons
No entanto, isso não resolve o problema do download da rede durante a instalação. Se você está fazendo um monte de instalações, você pode querer considerar a personalização do instalador via pré-configuração ou kickstart ou algo assim.