This is a fantastic puzzle, one of the best I have had to solve, so give yourself time to think it over. It took me a month to come to the solution.
To make you guys understand the solution, I will first demonstrate it in a particular case where there are just two colors. I will then expand it to N colors.
Preliminary logical deduction:
The fact that the prisoners are in line adds nothing to the puzzle. Once the first prisoner has talked, there is no difference in being the 9th prisoner to talk or the 11th, or the last: they will all hear what has been said before, and they can all see the colors of the hats of the prisoners ahead of them in the line. As we know that the 99 are saved, they all have the same information: the color the first prisoner said, and the colors of the 98 other prisoners' hat.
So let's first assume that there are only black and white hats. The prisoners agree that they will count 0 for black hats, and 1 for white hats. The first prisoner quickly counts the PARITY of the black hats, and says WHITE if it's even, BLACK if it's odd. Now all 99 prisoners can deduce the colors of their hat by counting the parity of black hats in front and behind them.
It gets a bit trickier with N colors, but the same idea leads to solution. The prisoners associate a number to each of the color. 0 for green, 1 for red, 2 for blue, etc. The first prisoner computes the sum of all the colors he sees, and the modulo of that number to N. He announces that number as a color. Now every prisoner can deduce the color of their hat, by computing the sum of the other prisoners' hat color and the modulo to N. Then if the number anounced by the first prisoner is 24 and I compute 22, I know that my color is blue, because adding 2 to 22 would give me 24, the number anounced by the first prisoner.