I think that I am having the same problem, the above solutions do not seem to fit.
I can add new categories in the Admin menu but they do not display in the admin menu or as an option when creating or editing a post.
I can see older categories that were created some weeks ago, but not the new ones. New categories do not display when I search for them but I can view the page if I go directly to the edit page and manually change the the ID in the URL, ie: https://www.xyz.org/wp-admin/edit-tags.php?action=edit&taxonomy=category&tag_ID=26&post_type=post, the category appears and is editable.
I can see all categories in the database in the xx_2_terms table.
Is this an issue of indexing?
I am using multisite. As far as I am aware, the only change has been that we went from a demo domain demo.server.org to xyz.org using domainmapping plugin. The server itself has not changed.