Hhuskies,
Having been through this problem myself, I'm hoping to offer some help. This may be a silly question but have you checked your memory_limit on your php.ini file? I think that was the ultimate source of woe for me. You can check your Apache error log and see if there is a memory error being triggered and if so, that could be the cause. I really thought I had already adjusted it, but I have three Linux boxes at work and a couple at home and so I guess I just mixed it up. Worth checking to save yourself trouble if you haven't already, as I learned the hard way. :)
Also, if you go and look under phpMyAdmin (or whatever tool you use) at the categories tables in the DB, are the category entries still there? That's what I saw, and so it added to my confusion, because they still existed, but the scripts just didn't see them.
I don't know that this will help but wanted to mention in case it does. Good luck and I hope it works for you soon!
Cheers,
Trase