Yikes, I just watched the Vista start menu demo. Lots of pseudo-cognitive psychology put me off this app for life...
Is the start menu dead? For me it mostly died in Windows 98 when I started using Litestep. Litestep of course required lots of tweaking, so the gains in productivity over the clumsy start menu were offset by writing config files to hone your interface Though I oscillated between explorer and alternative shells for app launching (and also task management where the start bar sucks) I was never quite satisfied. Until I found FARR. This was a Tarantino moment for the start menu, a complete gruesome yet swift death. As a mouse/keyboard flip-flopper I still can't get anything close to the power of find-as-you-type launchers mouse-wise.
I do like the concept of radial menus however; sapiens is a mac launcher that uses them (quicksilver also can use radial menus for key/mouse hybrid interface):
I don't know if there are app launchers in windows that use radial menus for launching (mozilla had a radial menus extension IIRC), but they offer several ergonomic benefits over the more common linear menus... Maybe a future Windows start menu will be round?