This should give you a different color at each keyframe. It does work differently because it has to go through all previous keyframes to calculate the current color:
colors = [[1,0,0,1], //red
[0,1,0,1], // green
[0,0,1,1], // blue
[1,1,0,1], // yellow
[0,1,1,1], // cyan
[1,0,1,1]]; // magenta
p = effect("Slider Control")("Slider");
seedRandom(index,true);
idx = Math.floor(random(colors.length));;
if (p.numKeys > 0){
n = p.nearestKey(time).index;
if (time < p.key(n).time) n--;
for (i = 1; i <= n; i++){
idx = (idx + Math.floor(random(1,colors.length)))%colors.length;
}
}
colors[idx]