Serialization failure: 1213 Deadlock found when trying to get lock; try restarting transaction

[Dante Lorenso]

All,

I am trying to create an atomic operation in MySQL that will manage a
"queue".  I want to lock an item from a table for exclusive access by one of
my processing threads.  I do this by inserting the unique ID of the record I
want to reserve into my "cli_lock" table.  The following query is what I am
using to lock a record in my queue:

INSERT INTO cli_lock (lock_id, object_id, lock_type, expire_dt)
SELECT $LOCK_ID, q.queue_id, 'parse', DATE_ADD(NOW(), INTERVAL 1 HOUR)
FROM queue q
  LEFT JOIN cli_lock l ON l.object_id = q.queue_id AND l.lock_type = 'parse'
WHERE l.object_id IS NULL
  AND q.status = 'parse'
ORDER BY q.file_size ASC, q.created ASC, q.queue_id ASC
LIMIT 1

However, as I execute this query several times each minute from different
applications, I frequently get these messages:

DB ERROR: SQLSTATE[40001]: Serialization failure: 1213 Deadlock found when
trying to get lock; try restarting transaction

Am I writing my query wrong or expecting behavior that MySQL doesn't
support?

-- Dante