It seems that if you add a new category in the cms whilst already inside a category, the drop down box that will define the new categories location is not set to the correct location automatically.
This was the case in 3.x. The url when creating the new sub category is :
admin_category_edit.php?parent_category_id=
So it seems clear that this empty parameter is the problem.