I just tested Skeleton on a site that was upgraded from D6 to D7 and for some reason there's no Navigation. I tried placing a menu into the Header region as well, and still no joy.
If I remove the IF statement for navigation in page.tpl.php then the menu displays correctly, however having a look at other themes page.tpl.php the original code should work.
Not sure if this is reproducible by anyone but hoping someone can shed some light on this.
If I switch themes to say Bartik, then everything works as normal.