Ok. I created my own Thumbnails from screen captures, and named the same name as the corresponding movie file, dropped them in the right album folder, and they are showing nicely now.
However, at the Gallery level, it is using some random thumbnail for the album itself. I tried putting a thumbnail with the same name as the album at the "albums" folder level, but it didn't work. Where are the thumbnails for the albums stored/retrieved-from ?