I don't think you are doing anything wrong. The Fire seems to hold onto the initial cover image it gets for a particular ebook forever. I tried deleting an ebook from the device and then reloading the modified version, but this did not help.
Note by "cover" I mean (and I assume you mean) the thumbnail that shows up in the catalog. The actual cover in the ebook does get changed, as you can confirm by opening the ebook on the Fire and navigating to the cover.
The only thing that might work is to change whatever the Fire is using to identify the ebook. This is probably the Amazon ASIN.