ptvguy, I'm not sure I follow your explanation, might be because it's late and I'm about to crash into my bed :P sounds to me like you're attributing the problem to updating the timestamp to a later date? If so that's not the case with mine as I know at least a few of these have never had their timestamp touched.
The two categories I knew were missing have returned after I switched to another server (for unrelated reasons) but now there are 10 others missing, some of which are some of the newest categories I've created.
Also noting that when I moved to a new server, I did a completely fresh install of WP, although I did import the old data from the previous host.
Again, every single category has at least one post as I don't create categories until I need them. I'll check in tomorrow.