I built a new menu, so why does my header still show my categories?

The header doesn't use a menu you create. Its main navigation shows:

1. Primary Menu, if it has any links.
2. Otherwise Main Menu.
3. If both are empty, your categories, and failing that Home, Shop, About and Contact.

A new menu you create appears in the list with (custom) after its name, and the header doesn't show it. A few header designs show your categories in place of a menu.

To fix it, go to Settings → Appearance → Layout Settings, Menu tab. Pick Primary Menu in Select a menu to edit, add your links, and click Save Menu.