Fading Colours in Blender Render
You can animate the Diffuse color parameter :

Put your mouse over the color selector, press I to insert a key. The color selector should be highlighted in yellow to show that a key is present.

Move a few frames forward, change the color, then insert a new key.

(You can do the same with almost every parameter)