Hello,
Please check your server error log. Fix warning and errors that relate to the server side, maybe you have a warning that relates to PHP. One of our clients had a similar problem with brands, the problem was fixed from the server side – https://www.8theme.com/topic/error-404-for-brands/
If this doesn’t help, check 3rd party plugins on your site, make sure that additional plugins do not affect the functionality of permalinks.
Regards