Hi Jason
I've been testing your staging site this morning, which has concluded with Types 3.4.15 being installed and the re-ordering working as expected.
I first confirmed it was working with the installed Types 3.4.5.
I clicked the link to update Types, which failed. (I didn't investigate this; I suppose the key was linked to the production URL rather than this staging site URL.)
So I manually updated, initially testing 3.4.6 and then several other versions before finally arriving at 3.4.15.
The first time I did that I de-activated Types first, and after re-activating the updated plugin found that the Advanced Post Type Order settings currently in use appear to have been lost. I went to recreate them, upon which a notice at the top indicated there was an existing re-order that would be used (i.e. the original re-ordering), and following that link I was able to resume working with the original re-ordering.
That didn't happen with subsequent Types updates, where I simply uploaded the plugin files to overwrite the existing install (through the Add New Plugins page), without first de-activating it.
Types is used to register the custom post types and taxonomies, and if it is deactivated (even temporarily) then Advanced Post Types Order can no longer reference them. Without digging into the exact steps, I think that is why the re-order settings are temporarily lost.
Anyway, as to the issue itself I didn't encounter any problems, the re-ordering continued to work with whatever version of Types I had installed, including up to Types 3.4.15.
That's the current state of the site, if you can verify that for yourself.
What is your workflow for updating production? Pushing changes from a staging server?