Comment 13 for bug 349607

User tests confirm this is live in a fresh install of Karmic. If the first thing you do is try to open a restricted codec gnome-codec-install will fail. Going to Software Sources and checking that everything is checked will fix the problem.