I wouldn't worry too much about the visuals of the UI at this stage, if the architecture is functional. I tested with 7-8 menus and didn't really think there was any scalability problems. How often do you use more than 3 menus on a site ? Maybe I misunderstood the scalability issue though, is it an issue if you have zillions of posts or pages ?

"The masses" will always complain about new UI`s and new design patterns, but with WordPress.TV it should be possible to make some official Menu UI introduction videos, and have links to them in the help tab.

John Myrstad