I'm having a very similar issue. I use dreamhost, upgraded from 139 to the newest 151 version of Zen. Because of my database size, I couldn't do a export from the old database and import into the new database, so I did the synchronize databases thing instead, then once that was done, I turned off the synchronize, ran the install again to upgrade the database, and it looked like it worked. But, like the OP, I have a lot of products that are showing in the Category Counts, that aren't showing up in the categories. Looking at the database under Products, they're all there, and there's nothing different about the missing ones, and the others that did work. Even the products that are in the same category, I'll have 8 actually there, and 4 being ghosts.
There is a difference in the Products total and the Products_Description totals, 961 Products, and 480ish listings in the description db. What's the most efficient way to fix this? Should I just insert the products into the Description table?
Attributes - I do have some, but many of the listings that worked came through with the attributes no problem.