Animating color changes in Keynote
One way to do this would be to have two objects that are exactly the same except for the color, in exactly the same position, then have one build out and one build in at the same time, with the effect set to dissolve. Doesn't work quite right.

You could also have two identical slides except for the color change, then set the transition between the slides to dissolve.