I am trying to replace a message from a function that got hooked in a constructor from a class from woocommerce.

This is what I tried to remove the message:

What I tried.

function remove_actions() {
    remove_action( 'product_cat_pre_add_form', array(   'WC_Admin_Taxonomies', 'product_cat_description' ));
}
add_action( 'plugins_loaded', 'remove_actions' );

Also instead of the first element from array ('WC_Admin_Taxonomies') I tried new WC_Admin_Taxonomies. Which returns true but it doesn't remove it because the instantiation adds the action, so it removes the current added action.

woocommerce/includes/admin/class-wc-admin-taxonomies.php - portion of interest

class WC_Admin_Taxonomies {
    public function __construct() {
        add_action( 'product_cat_pre_add_form', array( $this, 'product_cat_description' ) );
    }

    function product_cat_description() {
        echo wpautop( __( 'Old message', 'woocommerce' ) );
    }
}
new WC_Admin_Taxonomies();

This (_new->below) works fine, is adding the new message, but the code from first block (remove_action) above is not removing it, so I end up with 2 messages.

class WC_Admin_Taxonomies_new {
    public function __construct() {
        add_action( 'product_cat_pre_add_form', array( $this, 'product_cat_description_new' ) );
    }

    function product_cat_description_new() {
        echo wpautop( __( 'New Message', 'woocommerce' ) );
    }
}
new WC_Admin_Taxonomies_new();

Based on kovshenin answer I tried:

function instantiate_globals() {
    $GLOBALS['inst'] = new WC_Admin_Taxonomies;
}
add_action( 'plugins_loaded', 'instantiate_globals');
function remove_actions() {
    remove_action( 'product_cat_pre_add_form', array(   $GLOBALS['inst'], 'product_cat_description' )); // var_dump() - outputs true but still not removing it, I believe that filter is the issue.
}
add_action( 'plugins_loaded', 'remove_actions');