If you try to playback a video in Totem and the necessary codec for the video is not installed, Totem directs you to Software to install it. Software fails to find it even though the codec is present in the enabled repositories.
Seems to work here. What repository and what codec is it?
Most likely related to 1435583.
Duping. Reopen if this doesn't turn out to be the same bug after all. *** This bug has been marked as a duplicate of bug 1435583 ***