It is possible but quite complicated...
First of all you need to translate the colors of your image into another color space. the RGB one doesn't hold the characteristics of human perception of colors if I might say. So if you want a good looking result, you'll need to use another one (like HSL).
See here for the different color spaces: http://en.wikipedia.org/wiki/Color_space
With HSL you could "move" some colors to another value, but keeping the luminosity and saturation parameters.
The biggest problem here is to know when to move a color an when to keep it in place, and I think the results might look odd with first attempts.
Also you might need to run some kind of color analysis before deciding which pixels in the image should have their hue component modified. For example you could use a canny edge detection algorithm to detect portions of the image where the colors are quite uniform, and use interpolation instead of color replacing on the edges detected. That's just an idea there may be a lot of other ways.
This is a broad explanation of how you could achieve this.
I think this link could give you some useful information about color manipulation in an image, this could be a start: How to harmonize a color image
Also a google search about Color harmonization
could give you some clues.
I've tried something like this some time ago, if I have some time I'll dig it up and can post the code used. There are some useful tools for color space conversion and such things in my code, it isn't optimized at all, but it's helpful when you're trying to figure out how to proceed.