The real WTF was probably the hiring agency that the hiring manager insisted we go through. I'm pretty sure they were coaching their candidates, but we couldn't break away from that agency for some reason (cough kickbacks cough). The answers were suspiciously similar.

But I don't know how much better I could have described what I wanted:

"I want a class for holding a queue of items in memory. The queue will only need to hold a few thousand items, and you don't need to worry about persisting it in case of a power failure or anything. The only wrinkle is that when an item is added to a queue it has a priority. Higher priority items need to come out of the queue before lower priority items, but items with the same priority should come out in the order they were inserted."