Slow performance selecting next message from custom queue
One thing that I didn't see mentioned in the indexes which you tried would be an index on (queue, status, id). If you put the id at the start of your index it mostly destroys the use of the index since you're looking for the "lowest one", which is meaningless until the other criteria is applied.
The ordering of the columns in an index can often be just as important as the actual columns themselves.
I would guess that your index isn't getting used because the stats aren't yet gathered for the index.
Check out this SO question. You can provide a hint in the query to force the use of the index(es) you created. If this helps, then running DBMS_STATS.gather_table_stats package for your table should force the update of stats, eliminating the need for the hint. Eventually the database will gather the stats on it's own (see Justin Cave's answer).