Use vector tools. You will be much happier for political maps. For example, a vector tool with a decent .svg import would let you alter borders. I built a similar world map for Shadowrun a long time ago. After cursing Photoshop for months, I had a finished product within several days after switching to Freehand.