There's a new callbacks-related set of functions in 1.7, you can read about it here:
http://api.jquery.com/category/callbacks-object/ I'm wondering if you might be making it more complicated than it needs to be, though?
Are you using changePage() to go to the same page, and forcing it to reload? Or is this a separate page, but a page that shares the same menu as the originating page, and you want the originating page to have the menu changes reflected in it?
If it's the same page, in my opinion you're probably better off making the changes using jQuery, and then calling the refresh() function (or something similar) to make it all appear. Otherwise, you may get into issues with caching and hitting the back button, although I'm not entirely sure on that. Regardless, I think it would be easier than creating a callback and changePage() function setup.
If it's a different page, I would use a global variable that the changePage() function sets to true to signify that this is coming from a menu creation event, check to see if it's true in the receiving page's pagebeforeshow event, and if so then when it's handled and you modify the menu you set the variable back to false (or something like that). The challenge with that, though, is that the originating menu will not be altered. You can remove() that originating page and cause it to be reloaded, but that would depend on where it's being reloaded from having the new menu item included (this is also a problem with your "remove all the divs" approach you mention above). The other approach is that you could change the menu items across all of the pages by selecting both the visible and invisible menus in the DOM and modifying them, e.g., by using the same classes on them and selecting that class in the selector.
Anyway, you can probably do it with callbacks too, just wanted to offer some other suggestions.