Are you sure your custom menu disappears, or is it that the new theme doesn't display it?
It may be that the new theme doesn't support custom menus, or that you simply have so associate your custom menu with the theme location for the new theme.
I've just tried swapping from a twentyten child theme with a custom menu to a theme that doesn't support custom menus.
My menu didn't display of course, but in the back end (Appearance -> Menus) the menu was still there , but I couldn't do anything with it.
I then swapped to twentyten, and again it didn't automatically appear, but in the back end I simply assigned my custom menu to the 'primary navigation' menu location and voila! it now appears.
Now when I swap between the twentyten child and twentyten, they both display my custom menu, WP doesn't forget once you have assigned it, but the assignment is per theme, so you have to do it for each new theme.
Hope this helps,
Mike
--