Ah, you seem to be saying that nautilus doesn't do the thumbnailing itself, but is dependent on an external player.  Here are the relevant settings:

potpal:[~/Videos] gconftool-2 -R /desktop/gnome/thumbnailers 
 disable_all = false
 /desktop/gnome/thumbnailers/application@x-dvi:
  command = evince-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@xspf@xml:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@flv:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-avi:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-ogg:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-shockwave-flash:
 /desktop/gnome/thumbnailers/application@x-gnome-theme-installed:
  command = gnome-theme-thumbnailer %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@pdf:
  command = evince-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/text@x-google-video-pointer:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@quicktime:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@msvideo:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-flash-video:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-quicktimeplayer:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-extension-m4a:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/image@x-bzeps:
  command = evince-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/misc@ultravox:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-gzpostscript:
  command = evince-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-extension-mp4:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-ms-wmv:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-mpeg:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /<email address hidden>:
  command = evince-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-netshow-channel:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/image@x-pict:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-ms-wmx:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@sdp:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /<email address hidden>:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/image@x-gzeps:
  command = evince-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-matroska:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-flc:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@mp4:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /<email address hidden>:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-ogm@ogg:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/audio@x-pn-realaudio:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@msword:
 /desktop/gnome/thumbnailers/video@x-msvideo:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-ms-asf:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@mpeg:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-quicktime-media-link:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-cbr:
  command = evince-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-flic:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/image@x-eps:
  command = evince-thumbnailer -s %s %u %o
  enable = true
 /<email address hidden>:
 /desktop/gnome/thumbnailers/application@smil:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/text@google-video-pointer:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-theora@ogg:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-fli:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-nsv:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-bzpostscript:
  command = evince-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-bzpdf:
  command = evince-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@mp4v-es:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@vivo:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /<email address hidden>:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-font-pcf:
  command = gnome-thumbnail-font %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@fli:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-font-type1:
  command = gnome-thumbnail-font %u %o
  enable = true
 /<email address hidden>:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@postscript:
  command = evince-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@ogg:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-cbz:
  command = evince-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-gzpdf:
  command = evince-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-gnome-theme:
  command = gnome-theme-thumbnailer %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-ms-wm:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@ram:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-font-ttf:
  command = gnome-thumbnail-font %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@3gpp:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-m4v:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /<email address hidden>:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@dv:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /<email address hidden>:
 /desktop/gnome/thumbnailers/application@x-smil:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-matroska:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-shorten:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-ms-wvx:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/video@x-anim:
  command = /usr/bin/gnome-video-thumbnailer -s %s %u %o
  enable = true
 /desktop/gnome/thumbnailers/application@x-font-otf:
  command = gnome-thumbnail-font %u %o
  enable = true

and the gnome-video-thumbnailer alternative:
lrwxrwxrwx 1 root root 37 2008-04-20 22:56 /etc/alternatives/gnome-video-thumbnailer -> /usr/bin/totem-xine-video-thumbnailer

so totem-xine seems to be doing the thumbnailing.