Categories are different object type and due to old design, done through a binding table, the actual change is done in the documentcategory object type. So, if you want to clear cache when new category is added (to any page) you can use cms.documentcategory|all
key