Why does this simple transaction deadlock with MySQL?
I'd say it's an illustration on how gap locks work -http://dev.mysql.com/doc/refman/5.7/en/innodb-locking.html#innodb-gap-locks  .  

Say you have adjacent user id , 1 and 2.  When procedure executed simultaneously from 2 different sessions, each of them put a gap lock on two index-records (with user_id values 1 and 2 - maybe 0 ,4,5 as well ,but let's assume just 2 for simplicity sake), and each of them has to wait for another one to release the lock to perform an insert. 


  Gap locks in InnoDB are “purely inhibitive”, which means they only
  stop other transactions from inserting to the gap. They do not prevent
  different transactions from taking gap locks on the same gap. Thus, a
  gap X-lock has the same effect as a gap S-lock *." 


To disable locks,


  Gap locking can be disabled explicitly. This occurs if you change the
  transaction isolation level to READ COMMITTED or enable the
  innodb_locks_unsafe_for_binlog system variable (which is now
  deprecated). Under these circumstances, gap locking is disabled for
  searches and index scans and is used only for foreign-key constraint
  checking and duplicate-key checking.


Using READ COMMITTED sounds like a reasonable solution to me, assuming it doesn't break application logic.