A few years ago I wanted to color one person green (like the Grinch) in a photo as a joke so I pulled up GIMP and got really frustrated and eventually gave up.
Turns out it can be done by adding a layer of solid color, and masking around the subject.
I added another layer in between to switch the cat's color to black and white first, but I'm not convinced it was really necessary. (Also, Guido is a solid grey cat which brings up the question of why I thought it was a good idea.)
So... I've made him very, very purple. But at least I know how to make someone green the next time I want to.