I think I have fragments of memory that I had this same problem years ago.
Can't recall for sure, but I think it was related to the URL structure in Admin Panel. Try selecting one of the upper URL options and make a new attempt to create categories.
Admin > General > URL structure