Has anyone ran into this replication breaking bug before?
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.