I fixed this by changing the action I create the menu items from admin_init to admin_menu. The former runs far too early and I suppose was creating conflicts. I am now able to reorder my items by referencing them by their original slugs.
For future reference and in case it is helpful to others, the WP documentation for add_menu_page specifically recommends hooking to admin_menu.