I's like to have a workflow rule fire when a record is owned by queue A and then changes owner.

What I have so far is:

AND(
ISCHANGED(OwnerId),
PRIORVALUE(OwnerId) = 'QueueId'
)

I've tried both the QueueId and just the Id of the QueueSObject for the PRIORVALUE check.  The rule does not fire. Is it not possible to look up the OwnerId prior value at that time when the rule is evaluated?