This was my solution, and it does work for arbitrary cardinalities of colors and prisoners, as long as you're okay with the prisoners remembering arbitrary amounts of information. :)

Even harder version, to which this problem was a hint (and which I haven't solved yet, so please continue to ROT13 solutions):

There are countably many boxes 1,2,3,..., into each of which Alice places an arbitrary real number. Bob then opens finitely many boxes, looking at the real numbers they contain as he goes, and then names a single real number and opens a single unopened box. Bob wins if that box contains the number he named. Bob may condition his choice of boxes to open on what numbers he has already seen, and at each time step, he may choose the next box to open by random choice out of finitely many boxes that he identifies at that time step. Show that Bob has a strategy such that no matter how Alice chooses her real numbers, Bob wins--correctly predicts a real number--with very high probability.