Very quick post just in case it can help anyone out there …
Recently upgraded from Linux Mint 15 “Olivia” Mate-Desktop to Linux Mint 16 “Petra” MATE and had lots of problems getting thumbnails for anything but image files to work (regardless of what settings I used in Edit > Preferences > Preview in Caja). Finally stumbled across a solution here that worked for me. A quick install of Evince (which kind of was and wasn’t there), and I had thumbnails back for .cbr and .cbz (comic book archive) files.
After a bit of digging around, I discovered that Totem wasn’t installed, for some reason. A quick install, and I had video file thumbs back, too!
Both were installed via Synaptic, but I’m sure they could also be installed through the Software Manager or apt-get.
Hope that can be of use to someone! 🙂