I sort of had the same impression as many folks about the icons. However from what I've seen its common for traditional Japanese paintings to use red and black for the calligraphy and characters (example 1, example 2, example 3), so I think you are in keeping with the tradition here. What I think looks problematic perhaps is the the contrast between soft translucent watercolors and bold opaque colors. If you look at the calligraphy of the last image it looks softer and more faded. I think something like that would look better for this style of map, it would give the impression that these symbols were painted onto the map.

Cheers,
-Arsheesh