Listen to my story and learn from my mistake.
I was diligently working in Calibre over the weekend, adding newly-downloaded books, updating metadata, organizing, dusting, polishing... Finished my work, connected my Kindle, ran the Collections preview plugin; and got WILDLY wrong results! Half my tag-generated collections are missing. And the ones that are there are mostly wrong; generated from the wrong device, spelled wrong, prefix characters are wrong, just wrong, wrong, wrong.
Moderate panic attack; OMG what did I break? Disconnected Kindle, reconnected, re-ran preview. Still wrong. Checked the tags in Calibre, they're okay. What's going on? Upgraded Calibre, checked for plugin upgrade. Re-ran preview. STILL broken. Aw nuts. Opened the plugin, checked the config -- it's missing! WTF?
Deep calming breath, and gave myself a pep talk. It's late, you're tired, the collections on the Kindle are still okay because you've only been running the plugin preview. It's just the new books that won't be sorted properly. New books -- the ones that live in the Calibre Library called "Rough" until you've had a chance to convert them to mobi, add/update the metadata and covers, and just tonight were copied over to your main Calibre library.
The library.
I had Calibre pointed at my Rough library.

Where there is no Collections plugin config. Where the tags are mostly wrong until I'm ready to move the books over to the main library.
Pointed Calibre to the main library, re-ran the Collections preview and... everything is just fine. *Whew*.
If there's a moral to this story it's probably "Don't Panic".