Combining colorless base sprites with palettes?

[Barack Obama]

In my signature you can find a tool called Recolour v.1.6 by Previous Studios, this one can actually swap palettes very easily, if the picture information isn't too much (like file size).