You can also use CSS to achieve these kind of effects:
Changing the side columns not to scroll would need a major rethink of Moodle's navigation but having a fixed header (with or without some kind of navigation) would probably be possible just by changing the theme.
There's a few hierarchical menu implementations in javascript that are valid XHTML + CSS and will degrade okay when you turn off javascript or use a text/audio browser. You can even do it with just CSS, rather than javascript.
The real usability drawback of these things affects the people that actually see them as the designer intended because they usually require pixel perfect mouse control to operate. If you want to experience frustration then try using most of these javascript menus with your mouse in the wrong hand to simulate poor motor skills typical in older people.
The menus built into your operating system have a variety of code to make them easier to use, the Mac in particular does some very clever stuff based on the direction in which the mouse is travelling, rather than what area it covers, but even then I'm fairly sure the Apple HIG recommends against overusing them. Very few of the the web implementations are even aware there is a problem and so do nothing to make them more usable.
7 tricks that web users don't know: #3 Rollover Menus
A Quiz designed to give you the Fitts - an article about the usability principle called Fitt's Law see Question (and Answer) #6 for why submenus on the Mac are easier to use than submenus in Windows, which are in turn easier to use than web implementations.
Users decide first, move second - an article with a focus on why hierarchical menus are bad for discovery and search.
Looks very nice, though the jump to menu and the logged in as info move around depending on where you are in the site. Maybe the logged in username should always be at the bottom?
What about the other suggestion (possibly made by you, I can't remember) to highlight the existing 'back to front page' link, perhaps changing the text to 'Return to [course or moodle shortname] main page' or similar and moving it above the new nav-bar. Is that going to be part of the standard theme in 1.5? Because I thought that was a good idea too.
I've entered bug 2791 for this. The possibly misleading "Answer:" and the use of more instructive hints are possibly two seperate bugs, but fixing one would also fix the other so I've just entered one.