WordPress: “You don’t have permission to do that.”
You: “What!? I’m an Administrator! I can do what I want damn it!”

Until a fix is released a workaround for adding a new category is to simply fill the Category name:, Category slug:, Category parent: and Description: (optional) fields as usual but click on one of the input fields and press the Enter key. By avoiding use of the Add Category » button you can still add new categories to your install of WordPress in harmony.