I was running into the same issue, and I figured the Kindle was using some metadata to determine the right cover to download (despite me having provided one when I uploaded the books). So I went to the Amazon page for the particular books with the cover I wanted, noted their ASIN / ISBN-10 and ISBN-13 numbers, and modified the metadata in Calibre. In particular, I set the Ids field to:
Code:
isbn:<ISBN-13 minus the dash>, amazon:<ASIN or ISBN-10>, asin:<ASIN or ISBN-10>
Once I set these and uploaded the books, the Kindle pulled the cover images from the right version of the book.
P.S. - For good measure, if you have Amazon.com set up as a metadata source, once you set the Ids field you can click to Download covers and the Amazon.com cover should be the one you'll get on the device.