So, I tried to play with it and probably found a bug:
1) After activating plugin, options autosort, adminsort and level are created by default with function CPTO_activated().
But on Options page, there is following part of condition:
if (!isset($options['allow_post_types']) || ...
And this is always true, because allow_post_types is not defined after activation. So user can see that all post types checkboxes are checked by default (even if they are really not).
It leads to following error:
Notice: Undefined index: allow_post_types in plugins/advanced-post-types-order/advanced-post-types-order.php
And this error is related to this check:
... && !in_array($query->query_vars['post_type'], $options['allow_post_types'])
So, this is always true because $options['allow_post_types'] does not exist and fires mentioned Notice.
2) And that is why automatic sorting works in this case. But when you have option allow_post_types defined then automatic sorting really does not work. And the problem will be probably hidden in checking $query->query_vars['post_type'] because by default it is empty string for example on category archive pages. And plugin conditions does not work with it, because empty string is not in array of allow_post_types options, so as a result everything ends with returning default $orderBy variable.
Maybe related: http://core.trac.wordpress.org/ticket/19471