From what you describe, it's supposed to work.
Try clearing all system cache tiki-admin_system.php?do=all just in case.
Can you reproduce on a site where we can login and go an see?
Perhaps you have object permissions which are overriding the category permissions? Please check tiki-list_object_permissions.php for hints.