Také se mi to stávalo u asf streamů. Doinstaloval jsem potřebné moduly a pluginy a bylo vyřešeno. Ty pluginy se jmenovaly jako jeden western s C.Eastwoodem:
gstreamer-0_10-plugins-good
gstreamer-0_10-plugins-bad
gstreamer-0_10-plugins-ugly
Plus mraky dalších. Nyní jsem na stroji s openSUSE, takže nevím, jak to má Ubuntu, ale mělo by to být stejné. U každého modulu i pluginu bylo v popisu, jaké soubory to přehrává. Takže opravdu záleží na tom, jaké streamy chceš poslouchat.
PS: VLC není všelékem, protože pro soubory, které nativně neumí také používá gstreamer (pokud je k dispozici).