From what you describe you experience a problem that looks like a local problem on your site. Therefore the assumption is very likely that it is a configuration issue on your site and not a bug. Bug would mean this is a defect in the software. If it would be a bug, everybody using wordpress would run into this problem (or at least a great share).
Because this is not the case (for example I still can do what you describe as broken on my Blog), you need to find the problem within your blogs configuration. For example, please switch your site to the default theme and deactivate all plugins. Then test again, if you can or can not assign categories to posts.
If you still can not add categories to posts your site is very likely to be broken in configuration. Consider to contact professional wordpress support then to drill down this on your host because the reason of your problem can not be genreally found out w/o taking a look into your files and database(s).
If you can add categories after deactivating all plugins and themes, then it's highly likely that one of the Add-Ons is breaking stuff. You can now use try-and-error to find out which one of the Ad-Ons is causing this. It might be a single one (so to activate one and deactivating all others to find out) or a combination of many (so to activate group of plugins and then to test for functionality to find out).
Even these problems do occur often with third-party plugins, there is no tool or help build into wordpress that makes looking for a destructive plugin easier than doing a manual, one-by-one search.
Some trick at least is to just rename the plugin directory which temporarily prevents worpdress from loading all active plugins. Doing so makes looking for this being a plugin issue much faster than clicking through the plugin configuration in the admin.