I'm not sure you can achieve this with any specific set of colours - because there are a wide range of different ailments grouped under the term "colour blind".
No single scale that is based solely on hue is going to suit everyone - make sure you have variations in brightness as a minimum, and I'd recommend texture as well.
Here's a mockup, based on your original image:
Most people have three different colour receptors (Cones) in their eyes - red, green, blue.
The most common forms of colour blindness stem from a defect in one of these, where perception of that particular frequency is deficient in some way (lowest/highest perceptible level, distinction of different brightness levels etc).
Rarely, people may have only one or two kinds of cone, resulting in bichromatic or monochromatic vision.
Interestingly, a very small percentage of women have four kinds of cone - there are actually two kinds of green cone in the general population, and some women have both. These women have a greater perception of colour than usual, for example seeing up to 12 colour bands in a rainbow instead of the usual 7.
Disclaimer: I'm not an expert in this area, just a software developer who is yellow-green colour-blind who used to work for a data visualization company.