here's a crude way. open gif in imageready -> edit in PS
just go to the menu like shown, n if you're trying to replace relatively solid colors like that kitten's eyes, it should be enough.
just fuck with the fuzziness bar if it's showing thin outlines of another color.
make sure preview's on, so you can see the actual color before you apply change.
this doesn't work so well if you're trying to replace gradients or shit like that, where the color alternates quite a bit.

or you can grab yer pencil + zoom in to like 1200% and recolor by hand if it's smth tiny ~_~