MariaDB replication works via MASTER_LOG_FILE, almost instantly fails using MASTER_USE_GTID

We have a weird issue with MariaDB version 10.4.28+maria~ubu2004 (the official binary release for Ubuntu 20.04 LTS).

We dumped the master data using mariabackup (we have a single database), and restored it on a replica server exactly how it's described here.

Prior to restoring, the replica did not contain anything other than built-in MySQL/MariaDB databases and tables (information_schema, mysql and performance_schema) - all of this was populated automatically by the APT installation script.

The issue is we are unable to start replication using GTID but it works perfectly when using binlog, so:

{{
CHANGE MASTER TO
MASTER_HOST="dbserver",
MASTER_USER="user",
MASTER_PASSWORD="password",
MASTER_USE_GTID=slave_pos;
START SLAVE;
}}
Results in a failure almost right away, e.g.

Last_Errno: 1452 Last_Error: Error 'Cannot add or update a child row: a foreign key constraint fails

Or something more sinister like

Last_SQL_Errno: 1032 Last_SQL_Error: Could not execute Update_rows_v1 event on table database.tableX; Can't find record in 'tableX', Error_code: 1032; handler error HA_ERR_KEY_NOT_FOUND; the event's master log mariadb-bin.000009, end_log_pos 748324751

Whenever we setup replication using binlog, e.g.

{{
CHANGE MASTER TO
MASTER_HOST="dbserver",
MASTER_USER="user",
MASTER_PASSWORD="password",
MASTER_LOG_FILE='mariadb-bin.000001',
MASTER_LOG_POS=12345;
START SLAVE;
}}
It's working perfectly. Any help trying to understand or fix GTID replication would be highly appreciated.