I know you can do this in the GIMP, and it should be possible in PS, but can you not just do the solid fill on a layer above the other parts of the map, maybe below the text, and just set the individual layer's opacity to a very low number?