I recently had to deal with this error so I am blogging it here so the rest can use.
Error: On one of our tables we kept getting a duplicate key exception on insets. The puzzling thing was that the value actually did not exist in the table. Here's a low down:
Thats what was puzzling.
Did a lot of googling around but got nothing. I did get some hint that the issue might be with the sequences and that the sequence is not updated but got no clue on how to resolve the issue. Out of desperation I tried to see if the table was healthy and voila there it was. The table was corrupted. The solution was to either repair the table or get a copy from the slave. I tried the repair and it worked fine. I used local in the repair command as I did not want the repair to propagate to slave as the slave copy was fine. See commands below to check and repair a table.