Description:
INSERT...SELECT.. FROM t1 UNION ... FROM t1 allows concurrent INSERTs into t1.

This will cause the binlog to contain queries in what appears to be the wrong order.
Really what is happening is that the INSERTs are occurring concurrently and being logged
in completion order.

Eg.

Thread 1.
# Query that takes 10 seconds to run.
INSERT INTO table SELECT field FROM t1 WHERE id < 10 UNION SELECT field FROM t1 WHERE id >
20;

Thread 2.
# Query that occurs during INSERT in Thread 1 -- no field with value 'foo' exists
already.
INSERT INTO t1 (id, field) VALUES (1,'foo');
# Query that occurs AFTER the INSERT in Thread 1.
INSERT INTO table SELECT field FROM t1 WHERE id=1;

Binary log looks like:
INSERT INTO t1 (id, field) VALUES (1,'foo');
INSERT INTO table SELECT field FROM t1 WHERE id < 10 UNION SELECT field FROM t1 WHERE id >
20;
INSERT INTO table SELECT field FROM t1 WHERE id=1;

If 'table' has a UNIQUE KEY on 'field' and the log is replicated, it will always result in
a duplicate key error. This executes OK on the master because the INSERT SELECT in Thread
1 does not pick up the new value with id=1 that is INSERTed during it's operation. 

This only occurs if concurrent INSERTs are enabled and a UNION is used.

How to repeat:
Something along the following:

Thread 1.
# Some long running INSERT
INSERT INTO t1 SELECT <fields...> FROM t2 WHERE ... UNION SELECT <fields> FROM t2 WHERE
...; 

Thread 2.
# While INSERT in Thread 1 executes.
INSERT INTO t2 VALUES (.....);

Suggested fix:
Ensure all tables in an INSERT INTO .. SELECT ... UNION SELECT ... style statement are
correctly locked.

This is so far only repeatable on 4.0.x; 4.1 seems unaffected.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/internals/24058

4.1 is affected too. Just make sure t1 is not the first table in the UNION. E.g.

INSERT INTO table SELECT 'foo' UNION SELECT field FROM t1 WHERE id > 20;

Fixed in 4.0.25 and 4.1.12