All categories are still gone

I am having the same issue as this issue but their solution isn’t working.

http://wordpress.org/support/topic/251-all-categories-gone?replies=5

Basically my categories and tags keep dissapearing. The most commonly used ones still show up in the next tag but even when they are selected they don’t stay when I publish, edit or modify. Does anyone have any ideas how to get my categories and tags to come back.

I installed a new tags plug in and they stayed. Should I use a categories plugin?

I get to this step where they have this url…mine is a bit different and posted below.

Here is the one from the example:
yoursite.com/wp-admin/categories.php?action=edit&cat_ID=XXX

Here is mine…it points to tags instead for some reason:
mysite.com/wp-admin/edit-tags.php?action=edit&taxonomy=category&post_type=post&tag_ID=53

Any help would be great. Thanks.