hm, lemme think… ok different ways:
1 - basic colours can be animated, thus you can change the colour easily by inserting keyframes for RGB
2 - if you use textures: pre-rendering you animated texture and map the avi to the object
3 - two objects with the two different materials/textures. make one object slightly bigger then the other, and animate the alpha value of the larger object until it disappears.
4 - post-production/compositing. render each object once with alpha, render the background separately. in the sequence editorplace the bg first, then object one and object two. make a transition of the two object.
…no more ideas for now