WordPress Menu items that have children are not flagged as such until visiting the permalink of a child link. This gist forces a custom Walker on all calls to wp_nav_menu that adds a class to parents out of the box.

class.Iti_Walker_Flag_Parents.php

<?php

/**
* Iti_Walker_Flag_Parents
* Adds a class of 'menu-item-parent' to all WordPress Menu items that have children
*/
class Iti_Walker_Flag_Parents extends Walker_Nav_Menu
{
    function display_element($element, &$children_elements, $max_depth, $depth=0, $args, &$output)
    {
        $id_field = $this->db_fields['id'];

        if (!empty($children_elements[$element->$id_field]))
        {
            $element->classes[] = 'menu-item-parent';
        }

        Walker_Nav_Menu::display_element($element, $children_elements, $max_depth, $depth, $args, $output);
    }
}

// callback that sets a Menu Walker argument to be an instantiation of Iti_Walker_Flag_Parents
function iti_set_flag_parents( $args )
{
    return array_merge( $args, array(
        'walker' => new Iti_Walker_Flag_Parents()
    ) );
}

// we're always going to add our custom Walker
add_filter( 'wp_nav_menu_args', 'iti_set_flag_parents' );

Important to note that if implemented, this gist applies the Walker to all calls to wp_nav_menu