Remove all nav menu classes except those which begin with certain letters

array_intersect() is not a good choice when you need a partial match. Go through each class, and apply both checks before you remove a class.

Example, not tested:

function remove_menu_classes( $classes ) {

    // List of allowed menu classes
    $allowed =  array (
        'current-menu-item',
        'current-menu-ancestor',
        'menu-item-has-children',
        'current-post-ancestor',
        'first',
        'last',
        'vertical',
        'horizontal'
    );

    if ( ! is_array( $classes ) )
        return $classes;

    foreach ( $classes as $key => $class ) {

        // keep allowed classes
        if ( in_array( $class, $allowed ) )
            continue;

        // keep font awesome classes
        if ( 0 === strpos( $class, 'fa-' ) )
            continue;

        // remove the rest
        unset ( $classes[ $key ] );
    }

    return $classes;
}