remove_action not removing add_action from constructor

The thing with class methods is that unless they’re static, they belong to an object. And in your case your object is:

new WC_Admin_Taxonomies_new();

Which means PHP will create the object and keep it in memory. But unfortunately, since you’re not assigning this object to a variable, you have no way of referencing it later in your code.

Off the top of my head I can think of two ways to solve this:

First: globals, singletons, something you can use to keep a reference to your object for later use:

$GLOBALS['foo'] = new My_Class();
// ...

remove_action( 'action', array( $GLOBALS['foo'], 'method' ) );

Second: static methods.

class My_Class() {
    public static function init() {
        add_action( 'action', array( __CLASS__, 'method' ) );
    }

    public static function method() {
        // ...
    }
}
My_Class::init();

// ...

remove_action( 'action', array( 'My_Class', 'method' ) );

Hope this helps!