Hmm, that is really tricky! There's nothing wrong with a nice beautiful gray-scale map but as far as a solution to colors goes, maybe you could create a reusable pallet of "acceptable colors" with labels and just go back and use the color-dropper tool to reselect an appropriate color whenever you change?
You could have several pallets of colors with different labels: "Washed out", "vivid", "bright", so on? Then you could have subdivisions: "Grass, dirt, stone, lake, ocean" and so on. If you need a little help setting it up from the get go, you have a whole helpful community right here.