What you have discovered is because of the Inheritance rules used by Joomla!.
The Public UG is the Root UG. Guest, Manager, Registered and Super User UG's are all sons of Public. They start separate branches of the Family tree. Further, for example, Administrator UG is the son of Manager and the grandson of Public UG. All the sons, grandsons, great grandsons and so on inherit permissions of their forefathers. Deny is the special case that cannot be overridden further down the chain. Once 'denied' it cannot be undone lower down the tree
So for the particular Category set the Deny back to Inherited, do a Save. Then set the Registered to Allow and Save (NB the Save or Save & Close does the propagation of the permissions down the Tree).
Also each Top Level Category starts what could be called a new Clan of sub categories. Each sub category inherits the permissions ("genes") of its Father. So there is a double inheritance at work!! Deny permission can make a 'stop' in both sets of inheritance. Yes it gets complex!! The only safe place to use Deny is, in general, on individual Downloads as there are no children of a Download.