Dalla versione 7.04 puoi installare il metapacchetto ubuntu-restricted-extra
(mi sembra si chiami così).
Vedi cosa ti da synaptic