I think the problem is very simple to solve... and since I'm shit at explaining things, I'll use simple images to help.
It's all about the "color reduction algorithm" part of the optimization palette.
You just click that and make sure it's on Selective.
I think you saved it as web or some other one that skews the original colors in the optimizing(also remember to optimize the animation before saving aswell..that might be the problem too). I made a quick animation to show you the differences.