Here is what I am seeing
I see three queries, all almost identical.
UPDATE people SET company_id = 1610, name = '<name>', password = '<hash>', temp_password = NULL, reset_password_hash = NULL, email = '<redacted>@yahoo.com', phone = NULL, mobile = '<phone>', iphone_device_id = 'android:<id>-<id>', iphone_device_time = '2011-06-06 05:35:09', last_checkin = '2011-06-06 05:24:42', location_lat = <lat>, location_long = -<lng>, gps_strength = 3296, picture_blob_id = 1190,authority = 1, active = 1, date_created = '2011-04-13 20:21:20', last_login = '2011-06-06 05:35:09', panic_mode = 0, battery_level = NULL, battery_state = NULL WHERE people_id = 3125; The differences
TRANSACTION 1
iphone_device_time = '2011-06-06 05:24:42', last_checkin = '2011-06-06 05:35:07'
TRANSACTION 2
iphone_device_time = '2011-06-06 05:35:09', last_checkin = '2011-06-06 05:24:42'
Please notice that the column values are flipped. Normally, a deadlock occurs when two different transactions are accessing two locks from two tables with TX1 (Transaction 1) getting row A and then row B while TX2 is getting row B and then row A. In this case, it is TX1 and TX2 are accessing the same row but changing two different columns (iphone_device_time,last_checkin).
The values do not make any sense. At 5:24:42, your last checkin was 5:35:07. Ten minutes and 27 seconds later (5:35:07 - 05:24:42), the column values are reversed.
The big question is: Why is TX1 held up for almost 11 min ???
This is not really an answer. This is just bandwidth and throughout from me. I hope these observations help.
UPDATE 2011-06-06 09:57
Please check out this link concerning innodb_locks_unsafe_for_binlog : The reason I suggest reading this is something else I saw in your INNODB STATUS display. The phrse lock_mode X and lock_mode S. There may be some internal serialization going on doing next row locking. The default is OFF. After reading this, you may need to consider enabling it.
UPDATE 2011-06-06 10:03
Another reason to examine this line of thought is the fact that all the transaction are traversing the PRIMARY key. Since the PRIMARY is a clustered index in InnoDB, the PRIMARY key and the row itself are together. Thus, traversing a row and and the PRIMARY key are one and the same. Therefore, any index lock on the PRIMARY is a row level lock as well.