I did update my 2 Debian systems (unstable and testing) today, and the bug seems to have disappeared / been fixed All video thumbnails are generated properly in nautilus now.