Custom Taxonomies not retaining hierarchy while importing from one site to another

I understand your problem and had to work around it as well: wp_insert_term() doesn't handle parent/children connections.

You can check this with the following:

$tax = 'category';
$terms = get_terms( array( $tax ) );

$children_to_update = array();

foreach ( $terms as $term )
{
    $checked_term = get_term_by( 'name', $term, $tax );

    // ... retrieve parent here ...

    if ( ! $checked_term )
    {
        $term_data = wp_insert_term(
            $term,
            $tax,
            array( 'parent' => $parent )
        );
        if (
            is_array( $term_data )
            AND ! is_wp_error( $term_data )
            AND '0' !== $parent
        )
            $children_to_update[ $parent ][] = $term_data['term_id'];
    }
}
// inspect result
var_dump( $children_to_update );

You will see that it stays empty. The reason is simple: There's an Option that holds this information. You'll need to update it as well:

$option = get_option( "{$tax}_children" );
foreach( $children_to_update as $new_p => $new_c )
{
    if ( ! array_key_exists( $new_p, $option ) )
    {
        $option[ $new_p ] = $new_c;
    }
    else
    {
        foreach ( $new_c as $c )
        {
            if ( ! in_array( $c, $option[ $new_p ] ) )
                $option[ $new_p ][] = $c;
        }
    }
}
update_option( "{$tax}_children", $option );

At first I didn't get that the hierarchy didn't work, but when you look at the taxonomy overview page in the admin UI, then you'll see that the terms are not aligned like the should (in child/parent lists).