Color contrast is a tough problem! As Martijn says, hue is a good way to disambiguate things, however this exposes you to the difficulty of picking a clear color map. In their paper “Perceptually Driven Visibility Optimization for Categorical Data Visualization” Lee and friends highlight that discriminability problems arise for the related problem of categorical color maps (and develop a very slick solution for developing color maps).
If you don’t want to get involved with color, there are a handful of design alternatives that you might consider:
- Double encoding gray scale with texture (which can have the added benefit of making the display a little more accessible)–although the mapping of bin to texture should also be selected carefully to match the bin meaning
- Adding thick white lines as strokes around each of constituencies–although this may necessitate modifications to the shade of 5-10 bin.
- Switching the choropleth to be hex cartogram, so that each body in the map is given equal area–although this reduce the legibility of the representation as a map
There are of course other valid options, but these are some of my goto strategies for similar thematic mapping problems. The really tough thing about this problem is that there isn’t a silver bullet for all thematic maps like this, you just need to pay attention and make careful choices.