get_children() Not Working with orderby Parameter

Are you sure you need this specific function? Documentation (both Codex and inline) is verrry confusing. And it supposedly fetches things like attachments, which probably aren’t relevant for navigation…

Try this:

get_posts( array(
    'post_type' => 'page',
    'post_parent' => $parent->ID,
    'orderby' => 'menu_order'
) );