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
or
yum install gstreamer-ffmpeg

Once installed, I still had to remove the "failed" thumbnails (a placeholder so nautilus does not try to rebuild thumbnails for files it failed before). You can simply do this by removing the hashes:

rm -vf ~/.thumbnails/fail/gnome-thumbnail-factory/*

Then just open the folders to regenerate those thumbnails.