Ozh, I completely understand the reasons why you and deuts prefer to have the header area up there. I have only one blog so it works for me without it.

Have you thought about writing a plugin that splits the second level menu items in two columns in case there are too many of them to fit in vertically without scrolling?