Kubuntu 14.04, but I think it applied to earlier versions I've run.
Programs like Dragon Player and the video previewer in Dolphin routinely pop up a dialog box that says there is no H.264 decoder plugin available. Then the app searches the machine for a matching plugin and finds none. I've tried having all the gstreamer plugins known to mankind installed, but I still get the same error. I've had both 0.10 and 1.0 gstreamer versions as well. Some discussions about the problem online suggest using the 0.10 plugins, but even when I limit the machine to just that version, the problem remains.
Since nearly every video file distributed these days is H.264-encoded this is a very annoying error. Luckily you can use mplayer-based solutions since it has its own set of codecs. I presume this problem has something to do with patent issues surrounding the H.264 codec, but I always check the box during installation to install restricted-extras. I just forced the installation of both ubuntu-restricted-extras and kubuntu-restricted-extras, and Dragon Player still cannot find an H.264 decoder to use.