I use Gimp, but what I do with this is I just make a layer entirely for political borders... and when I want to adjust a border, I use a 1-pixel pencil to cut into a neighboring empire with the color of the conquerors. I then fill the new space with the conquerors' color, and voila! The pencil tool makes it easy to fill because it's hard-edged, as opposed to soft-edged paintbrushes or the like.