Has anyone ran into this replication breaking bug before? I've been having this issue where replication was breaking on colliding primary keys.  The annoying thing was these were auto increment generated.

I think my issues been tracked down to http://bugs.mysql.com/bug.php?id=45677 for a couple reasons


The slaves that were breaking were using triggers
Slaves with identical schemas sans triggers were not breaking
I was able to reproduce the problem following the reproduction steps in the ticket


What leaves a shadow of a doubt that's the exact bug that's biting me is the schema and application have been running for years with out issue.  It started happening shortly after upgrading mysql versions.  That might seem like a 'well duh' thing but it was an upgrade from 5.1.5 to 5.1.59.  The ticket indicates it's been around since 5.1.35, so should have bitten me much sooner, no?

If you've run into this what version were you running?
That bug is referenced in the MySQL Documentation for 5.5 and 5.1.40+ as that condition being unsafe.

Note the bottom of the bug report:


  [10 Dec 2010 3:34] Daogang Qu  Any statement that causes a trigger or
  function to update an AUTO_INCREMENT column is considered unsafe for
  statement-based replication after a patch of
  Bug#45827(http://lists.mysql.com/commits/9031). I had backported the
  patch to mysql-5.1-rep2 long ago. But I didn't see it in
  mysql-5.1-bugteam. The patch must be missed to merge to
  mysql-5.1-bugteam. I'm going to commit a patch to fix it in bug#45827.
  Thanks for the check.
  
  [10 Dec 2010 4:12] Daogang Qu  Sorry. The patch of bug#45827
  backported into mysql-5.1-rep2 should be merged into 5.5 instead of
  5.1. It's merged into 5.5 successfully.
  
  For 5.1, We mark all the statements that invoke a trigger or call a
  function that updated autoinc fields as unsafe and will switch to
  row-format in mixed mode. But in statement mode, we didn't emitted the
  warning.
  
  For 5.5, we emitted the warning in statement mode, because  a suppress
  warning feature is introduced.


Could a patch have been overlooked between minor releases of 5.1? That is the only probable cause. Now that Oracle is the grandfather of MySQL (via Sun), don't hold your breath for any fixes.

MySQL 5.1.59 was released Sept 16 2011 and this is still around?

It must have been an overlooked/forgotten patch.