ｎａｕｔｉｌｕｓを閉じて
$ rm ~/.thumbnails/fail/gnome_thumbnail-factory/*
してから今一度ｎａｕｔｉｌｕｓを開いたら「個別でアイコン表示」されませんか？
（ファイルマネージャ(ファイルブラウザ)がnautilusでない場合は
　"gnome_thumbnail-factory"とは違う名前かも知れません）


totem-video-thumbnailer (もしくは同じ機能の別のプログラム）が
どんな時に失敗してしまうかはよくわかりませんが
「色々試したところ」の色々はどんな事だったんでしょうか？

開いている窓にドロップしたとき(copy|move)
見えているフォルダアイコンにドロップしたとき(copy|move)
guiで見えていない状態で cp か mv したとき
...等々考えつきますがいかがですか？
移動|複写 先のファイルシステムによっては
thumbnailが抑制される設定になっていることも
あるかもしれませんが、今回は同じデバイスでの事ですね？
それからそれぞれの動画のコーデックによっても違いは
ありそうですが、これも今回は関係なさげ。
(基本的に「拡張子」←ファイルネームの最後の部分は
　ファイルマネージャ(ファイルブラウザ)が
　動画だと認識する限りあんまり関係ないはずで
　重要なのはコーデックです。
　つまり、着ている服よりは性格の方がダイジ)


# "個別のアイコン"のことを thumbnail といい、
# ~/.thumbnails/ 以下に保存されています
## 肥大するのでたまに掃除した方がいいかも

# こちらもどうぞ http://ubuntuforums.org/showthread.php?t=1337750