Originally Posted by Brian

Edit the category that you want to allow your users to create sub-categories in and make sure the 'Allow Users to Create Sub-Categories' is set to 'Yes'. Once you do that then they will be able to create sub-categories in that category via the 'Category Admin' link on the user side.