no the solution doesn't fail.
suppose there are 19 black and 1 red hat
then 20th last prisoner shouts black (key word for black being odd)
he does not know his own hats colour so he may or may not be saved
but the 19th prisoner knows that including his hat there are odd number of black hats, now if he sees even black hats, his hats colour is black, but if he sees odd black colours, his hat colour is red
now suppose he sees odd black colour, then he shouts red
the others keep on counting, this red means red is now odd (key word for red being odd)
the others would keep a note of it and carry on like wise