SELECT ... FOR UPDATE performance costs? alternatives?

All,

I have a stored procedure that I use to manage a queue.  I want to pop
an item off the queue to ensure that only one server is processing the
queue item, so inside PGSQL, use SELECT ... FOR UPDATE to lock the row.
  Here's how I pop the queue item:

----------------------------------------------------------------------
CREATE OR REPLACE FUNCTION "public"."reserve_next_tcqueue" (in_hostname
varchar, in_status char, in_new_status char) RETURNS bigint AS
$body$
DECLARE
     my_reserved_id BIGINT;
BEGIN
      /* find and lock a row with the indicated status */
      SELECT tcq_id
      INTO my_reserved_id
      FROM queue q
      WHERE q.status = in_status
      ORDER BY tcq_id ASC
      LIMIT 1
      FOR UPDATE;

     /* we didn't find anything matching */
     IF NOT FOUND THEN
         RETURN 0;
     END IF;

     /* change the status to the new status */
     UPDATE queue SET
       status = in_new_status,
       ts_start = NOW(),
       ts_end = NULL,
       hostname = COALESCE(in_hostname, hostname)
     WHERE tcq_id = my_reserved_id;

     /* send back our reserved ID */
     RETURN my_reserved_id;
END;
$body$
LANGUAGE 'plpgsql' VOLATILE RETURNS NULL ON NULL INPUT SECURITY INVOKER;
----------------------------------------------------------------------

When my server is under severe load, however, this function begins to
take a long time to execute and I begin to suspect that the FOR UPDATE
lock might be locking the whole table and not just the row.

How do I know if this is the case, how can I optimize this procedure,
and how should I be doing this differently?  I'm guessing stacks and
queues would be common patterns handled in the PostgreSQL community.

Thoughts?

-- Dante