The new “navigation menus” in WordPress 3.0 have nothing at all to do with the Parent Page and Menu Order controls on the page admin screen. They are totally different, duplicate, systems.
If you use both of them, you will have to manually re-create an identical setup in the “menus” admin screen. And then you will have to remember to manually resynchronize everything whenever you change anything.
As yet there is no way to load a sidebar widget into the new menus, nor can you embed a menu into a sidebar. For now we are stuck with this mess.