Comment 3 for bug 801295

Adding kubuntu-restricted-extras fixed the random access issue. I'm not sure which additional package made the difference, but arguably it should have been installed by the "installed missing packages" dialog, which I used to add the "sequential-only" MP3 playback.