[hDeraj]

I just started a similar project a couple weeks ago. After getting the prominent colors, recoloring the original image makes a pretty neat effect.

http://www.jaredharkins.com/posts/palette.html

[blu_jay]

I tackled the same problem. In fact, I utilized the same strategy you did. It is essentially the same, but allows for the user to input a gif and receive a reconstructed gif using only its "palette."

https://github.com/salkj/palette