I think I found something. I took a couple of epubs that wouldn't show the covers on the NC, converted them to mobi files, then back to epub after removing the original. The covers started showing up on the NC like it had when others tried that.
Then I opened up the new epubs and compared some of the files to the original versions looking to see what had changed.
Inside the epubs in a file called content.opf I found the following lines:
In the <metadata> section:
<meta name="cover" content="cover1"/>
And in the <manifest> section:
<item href="cover.jpeg" id="cover1" media-type="image/jpeg"/>
That "cover1" was just "cover" in the working epubs. It looks like when the NC scans a new epub it looks for something to have the id of "cover" in this file. If the cover image isn't assigned an id of "cover" then the NC doesn't use the image. I removed the '1' from those two lines in the original, non-cover, epubs and reloaded them onto the NC. Once I refreshed the epubs started showing with the right cover images.
This might not be the case for all files, but at least it's something that's easy to check/fix.