In VLC zijn inderdaad alle vereiste codex gebundeld: met VLC zou het wel moeten gaan.
Om de ondersteuning binnen het besturingssysteem te installeren, kan je tijdens de installatie van Ubuntu een checkbox aanvinken waardoor de vereiste software dan mee geïnstalleerd wordt. Heb je dit toen niet gedaan, dan kan je de software achteraf nog toevoegen. Die bevind zich in de "Multiverse" softwarebron. Mogelijk moet je die eerst activeren in "Software and Updates" or met het commando "sudo add-apt-repository multiverse". Daarna kan je de ondersteuning installeren:
sudo apt-get install ubuntu-restricted-addons