Each theme registers different theme locations in which to place the menu. If your new theme still supports WordPress 3 Custom Menus, all you’ll need to do is go back to Appearance > Menus, set your menu to the new Theme Location and activate that location with UberMenu (setup instructions steps 6-7). If your new theme does not support WP3 Menus, you’ll need to use easy integration.