What version of MySQL? Sounds like the old AUTOINC lock mode behavior. http://insatiabledemand.ideeli.com/post/18850015294/diagnosi...
I think that this is thread/mutex based because of the fact that I could try to run the same series over and over and get different sets failing. So it seems to me the issue might be something environmental affecting timing.
Again the really braindead thing here was that it was only one statement, only one concurrent transaction at any point in time.