I have a similar problem. Downloaded book from Gutenberg into Calibre. Somehow, by clicking on the wrong icon at the right time, I have wound up with a hideous cover (a blue thing that looks like a primitive hand-held games machine) instead of the right one. Went into the Edit Metadata area and got a pretty cover from one of the searched sources there. It appears as the cover in Calibre but every time I try to download it to the Kindle Fire, it comes up with the same hideous cover despite the fact that I have removed the original download from the Fire several times. The nice cover appears on the page after the hideous one when I open the book on the Fire.
How do I change the cover on the bookshelf on the Kindle Fire please? I've been banging my head against this wall for hours now!