I have this same problem and in my case the category missing does have posts linked to it.
http://damntalkingbox.wordpress.com/ – the second to latest post is placed in “Reviews” and when I posted that, Reviews did show up in the header. However, when I posted again today, despite the latest post not being in that category, it has now disappeared. I have tried to repost the post and marking the category again but it won’t show up.
If you want more to show, you can create a custom menu with all your categories in it and then in “theme location” set the secondary menu location to that new custom menu. Do be aware though that if the secondary menu goes to a second line, or if you have a lot of categories the menu section of the theme might break, and/or look really bad.