I've been switching between different media players and found that Totem-xine is the only one that plays all my videos well. I've been installing and uninstalling quite rapidly, so I think something might have gotten messed up in the process.

Anyway, I've tried every hint online. I've deleted the /home/.thumbnails folder. I've used gconf editor to change the command to /usr/bin/totem-xine-video-thumbnailer -s %s %u %o and it's enabled. It wasn't working for "gnome-video-thumbnailer" either. I also tried updating the thumbnailer to totem-xine-video-thumbnailer from gnome-video-thumbnailer through command line (sudo update-alternatives --config gnome-video-thumbnailer), but all I get is the response: "There is only 1 program which provides gnome-video-thumbnailer (/usr/bin/totem-xine-video-thumbnailer). Nothing to configure)."

One final note: I deleted the thumbnail folder contents a little while ago and no more "failed" folder is popping up, so it seem like the thumbnailer isn't failing to create thumbnails (maybe it isn't even trying).

Anyway, I'm not too sure what could be the problem. The other two fixes I mentioned worked for everyone else online, so I'm guessing it's some stupid setting that's off.