I can only guess that your theme isn't using the relatively new menu system and that no other changes you make in Administration > Appearance > Menus affect the main menu.
How are you setting up menus? If your theme doesn't support them (you might let us know which theme you are using), then yes, modifying header.php (in a child theme) as suggested above is the way to go. You can either
o find where the header.php creates the menus and modify that code to add the links that you want, or
o add code to functions.php and header.php so that it will recognize the Navigation Menus you define in the Administration > Appearance > Menus panel.
See http://codex.wordpress.org/Navigation_Menus for additional info.
If that's not clear, to provide additional help we will need info on your site's theme.