Since some time I was wondering why my Gnome did not generated thumbnails for various video formats (avi, mkv, ...) as thumbnails in my file browser (nautilus) really help me navigate.
Today I investigated some more, and even though I have the whole gstreamer-plugins set installed what I apparently needed was gstreamer-ffmpeg !
When RPMforge is enabled, simply do:
apt-get install gstreamer-ffmpeg
yum install gstreamer-ffmpeg