How did you recolor the animated bits? If you opened the gifs in an image editor such as Paint Shop Pro, or Photoshop, and recolored them that way, there is the problem. Animated gifs are actually several images in a strip, but only animated gif editors will read, and save all the frames. If you have Paint Shop Pro, you will also have Animation Shop. Open the original files with that and you'll see what I mean. Another option would be Gif Movie Gear.
