I thought this might help someone avoid the adventures I had yesterday. I did all this after the upgrade but it might be an idea to do it before as the upgrade doesn't keep your existing menu's intact anyway.
I don't think it matters which order you do this:
1. Orchard.exe > package uninstall Orchard.Module.Szmyd.Orchard.Modules.Menu.
2. Delete all Advanced Menu's.
3. Delete all Advanced Menu Widgets.
4. Delete Menu & Menu Relation Parts from all Content Types.
5. Add Navigation Part to all Content Types.
6. Re-create all menu's.
In Navigation/Content Menu Item/Add, the pop-up window throws some JS errors in use: "Cannot Perform Requested Operation" & "TypeError: menuText.val() is undefined" also the window has no vertical scroll bar so if you have a
lot of Content Items you can't get at all of them but you can add Content Items to a menu in the Content Items properties once the Navigation Part is added.