When backing up and restoring were you doing both the menus and CustomActions? The menus just use the ID for the command from Custom Actions (and that ID is not predtermined, so rebuilding the action list won't make the menus work).