In order to make sure that all of your Joomla category and section links work, they must be linked to from some menu.

I like my menus to link to blog formatted pages, so users aren't just looking at ugly links pages. Due to some bug in the core code, the categories and sections are assigned default IDs of 1 if you don't link them from a menu. When your header links are broken, you can fix it very simply. Create an additional menu, link to all of your content or section tables, and simply leave the menu unpublished.

It's a frustrating problem, but the solution is very easy.