Just had this problem. I tried several methods to change the covers. And succeeded, but I'm not sure which method worked.
1. After downloading the new cover, convert the book convert to ePub. (ePub to ePub overwrites the old ePub with the new ePub.) This will embed the new cover in the ePub file.
2. Using Windows Explorer, delete the old thumbnails on the reader e:/database/thumbnails/<all directories> (only try if nothing else works. Make a copy of the directory first, just in case.)
3. In Calibre | preferences | Sending books to devices: change "Metadata management" to Automatic. Attach your ereader to activate.
4 (If necessary, copy the ebooks to the reader again.)
5. When you open your ereader, page through your books. As you page through, you can see the ereader updating the thumbnails.
Some combination of the above five steps worked for me. Unfortunately, I don't know which of the steps are necessary and which are not.