This is weird, but I seem to have found a conflict with the multilingual qTranslate plugin.
What happens is -- with the default post types order settings -- my nav menus are all coming up empty. That is, a function like
wp_get_nav_menu_items( $menu_id ) returns an empty array.
If I disable the Auto Sort option, things return to normal working order.
Auto Sort does not cause the same problem when qTranslate is disabled.
This also only appears to happen on archive pages like the blog home, category archive, or cpt archive page (I haven't tested others). Single posts & pages don't appear to cause problems with both turned on.
I can't say for sure that this plugin is the source of the problem as it's conflicting with another, but due to the nature of PTO, it seems like the more likely offender.