Add body class of category parent

Use get_ancestors() to get the parent terms. Here is an excerpt from my plugin T5 Parent Terms in body_class:

    $ancestors = get_ancestors(
        get_queried_object_id(),
        get_queried_object()->taxonomy
    );

    if ( empty ( $ancestors ) )
    {
        return $classes;
    }

    foreach ( $ancestors as $ancestor )
    {
        $term          = get_term( $ancestor, get_queried_object()->taxonomy );
        $new_classes[] = esc_attr( "parent-$term->taxonomy-$term->slug" );
    }

This will work with any taxonomy, not just categories.