Can I have a different menu for each parent page?

On each (child) page, get the top-most parent, then display the according menu.

Here is a blue-print of what I just described (you may have to change this and that to make it behave like you want it to). Simply put the following code where you currently have your menu set up (in your header.php file, I suppose):

if (is_page()) {
    $id = get_the_ID();
    if (count($ancestors = get_ancestors($id, 'page')))
        $id = $ancestors[count($ancestors)-1];
    wp_nav_menu(get_post($id)->post_name.'-menu');
} else
    wp_nav_menu('default-menu');