Custom Permalink Plugin and Current Page/Ancestor in Menus

You could add classes to wp_nav_menu via the nav_menu_css_class filter:

function wpa83498_nav_class( $classes, $item ){
    // if Shop is the current menu item being output
    // and we're viewing a single product post type
    if( 'Shop' == $item->title && is_singular( 'product' ) )
        $classes[] = 'current-page-ancestor';
    return $classes;
}
add_filter( 'nav_menu_css_class', 'wpa83498_nav_class', 10, 2 );

EDIT-

Try this to see how the objects that make up a menu are constructed. Perhaps it will shed some light on how you can manipulate menu output. Look at things like menu_item_parent and object_id to see how menu items are related to each other and the posts / pages they represent. Warning- do not do this on a live site!

function wpa_inspect_menu_objects( $menu ) {    
    echo '<pre>';
    print_r( $menu );
    echo '</pre>';  
    die();  
}
add_filter( 'wp_nav_menu_objects' , 'wpa_inspect_menu_objects' );