If you create a custom menu, then you must add links. If your custom menu includes links to category pages, then each time you add a category you must edit your custom menu to include the new category page links to your menu.
If you add a category widget to your sidebar, does that automatically update? If so, then it is acting as it should.
But with a custom menu, the software does not automatically add tabs or drop-down items: the key word is "custom" so you must add them yourself.
Because your blog is not visible to me, I may be misunderstanding your response. If so, please clarify.