As the image does not have a lot of colors in it I am suprised you have that many problems.
I would first do is some frame optimization so only the color changing squares are modified in later images, leaving the static part only in the first frame. Those larger images should then only need 5x5 or 25 colors, As such no quantization or dithering should be needed for the second and later frames.
In fact if you quantize the squares separately to the rest first static image (just make the first frame use white for the squares and quantize down to leave at least 25 colors free), then you should be able to avoid any and all color problems. Of course each frame will have its own color table, but they should not need quantization (color reduction).
Divide and Conquer and you should avoid problems.
If this is for a web page you can make a "image table" with the static parts as separate images.
In fact as the squares are solid colors just generate a 5x5 pixel image and use HTML width and height image tags to set the final size. That will make your animation VERY VERY VERY small with no chance of dither noise at all!
For an example of an "imagetable" see...
http://www.cit.gu.edu.au/~anthony/wwwla ... rt/scroll/
and
http://www.cit.gu.edu.au/~anthony/wwwla ... rasterman/
though that was designed for a very old small browser window.
Also look at the other "HTML Art pages" in my WWW Lab
http://www.cit.gu.edu.au/~anthony/wwwlab/
remember 'view source' to see how it all works.