woocommerce_add_to_cart_validation is a filter that is run in the add_to_cart_action method of the WC_Form_Handler class.
This method is attached to the init hook.
add_action( 'init', array( $this, 'add_to_cart_action' ) );
Your taxonomy is quite probably also registered at the init hook. The WooCommerce action has no priority set, so the default would be 10. I would try to register your taxonomy with a higher priority (lower number), so that the taxonomy is definitely registered before the add_to_cart_action is run. (Just a guess, and not verified)