После того как захожу в папку с видео, в thumbnail/fails создается каталог gnome-thumbnail-factory в котором по мере заходов в каталоги с видео создаются png файлы размером 300-500 байт и размером имени в 32 символа.
Ну да, миниатюры создает totem, т.е. он должен стоят. VLC сносить вовсе не обязательно, просто поставь его параллельно с totem'ом. Более того, ты можешь поменять в свойствах любого видеофайла то, каким проигрывателем открывать его по умолчанию и тогда *все* файлы этого типа будут открываться выбранной программой.