Why can I not see certain categories in the Navigation Structure despite supposedly having access according to the category settings?
If a category does not contain any documents (i.e., is empty), it is hidden from users in the navigation structure until it contains documents. This means that once a document is published, the category and its documents will be displayed.
Note that this does not mean the user cannot publish documents in a category that is not visible in the navigation structure. The category will appear in the publishing dialog, provided the user has access to the category, of course.
Note: The above does NOT apply to users who, through their profile settings, have the ability to manage categories (see point 6), which grants them overriding access and means they can view all categories, regardless of whether they contain documents or not.