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