Originally Posted by CRussel
Try deleting the books from your Kindle, then restarting. Now add the files back and then write out the collections settings using Create from the Collections menu. (And restart again, of course.) I've seen this happen a few times with books that somehow have a slight disagreement between the Kindle and Calibre about which book is which. The Collections logic seems very sensitive.
Book ids stored internally or computed from file names have to match exactly, so as suggested it may be that you have a book on the Kindle which didn't come from Calibre or had its name/path/id changed at some point. Try the Edit Collections option in the plugin to look at the books in question to see if they are listed as in Calibre or not and to check for duplicate books. (Books can be added to Calibre from the Kindle using the Device icon and then right clicking on the book and selecting Add books to library).