Deadlock on inserts to a single table with a single key. (Mysql)
I guess you have following issue.

If a duplicate-key error occurs, a shared lock on the duplicate index record is set. This use of a shared lock can result in deadlock should there be multiple sessions trying to insert the same row if another session already has an exclusive lock. This can occur if another session deletes the row.
http://dev.mysql.com/doc/refman/5.6/en/innodb-locks-set.html