I'm not sure what's going on here, and I may be a little crazy, but I've been able to replicate this in a very simple manor, and I just hope I'm missing something obvious.

I've created a table with the structure of:

CREATE TABLE IF NOT EXISTS `test` (
`id` int(3) NOT NULL,
`val` int(3) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

And inserted a single row
INSERT INTO `test` (`id`, `val`) VALUES
(1, 1);

Now, if I run the following query:
UPDATE `test` SET `val` = 1 WHERE `id` = 1;

I receive the error of:
ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

Originally we have a galera cluster set up with 5 nodes on it. For the sake of ruling out collisions I've stopped all but one node. The cluster does not receive any traffic yet, as we're prepping to move our production sites to it. I will copy / paste my command line output showing the structure and queries that work / don't work below.

I have mysqld running in the console of the one node, and the console is showing:

131223 14:45:26 [Warning] WSREP: SQL statement was ineffective, THD: 5442, buf: 105
QUERY: UPDATE `test` SET `val` = 3 WHERE `id` = 1
=> Skipping replication
131223 14:45:26 [Note] WSREP: cluster conflict due to certification failure for threads:
131223 14:45:26 [Note] WSREP: Victim thread:
THD: 5442, mode: local, state: executing, conflict: cert failure, seqno: -1
SQL: UPDATE `test` SET `val` = 3 WHERE `id` = 1

Every time I receive the deadlock error. Which that error in itself doesn't really seem to be an error. However, because it is for some reason thinking it's a deadlock, it's trying to run it 4 times, because I have wsrep_retry_autocommit = 3.

mysql> CREATE DATABASE `test`;
Query OK, 1 row affected (0.01 sec)

mysql> USE `test`;
Database changed
mysql> CREATE TABLE IF NOT EXISTS `test` (
-> `id` int(3) NOT NULL,
-> `val` int(3) NOT NULL
-> ) ENGINE=InnoDB DEFAULT CHARSET=latin1;
Query OK, 0 rows affected (0.07 sec)

mysql> INSERT INTO `test` (`id`, `val`) VALUES
-> (1, 1);
Query OK, 1 row affected (0.02 sec)

mysql> UPDATE `test` SET `val` = 1 WHERE `id` = 1;
ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction
mysql> UPDATE `test` SET `val` = 2 WHERE `id` = 1;
Query OK, 1 row affected (0.01 sec)
Rows matched: 1 Changed: 1 Warnings: 0

mysql> UPDATE `test` SET `val` = 2 WHERE `id` = 1;
ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction
mysql> SELECT * FROM `test`;
-------+

-------+

-------+
1 row in set (0.00 sec)

mysql> UPDATE `test` SET `val` = 2 WHERE `id` = 1;
ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction
mysql> UPDATE `test` SET `val` = 3 WHERE `id` = 1;
Query OK, 1 row affected (0.02 sec)
Rows matched: 1 Changed: 1 Warnings: 0

mysql> SELECT * FROM `test`;
-------+

-------+

-------+
1 row in set (0.01 sec)

mysql>

I've also tested this with a table that does have a primary key set.
This was originally reported to https://groups.google.com/forum/#!topic/codership-team/wDtm6I_dZ9U , but they've said that it's most likely a MariaDB specific issue.