Can palettes be unambiguous for colour blind users?

I am making design recommendations for a piece of software that wants to accommodate entirely illiterate users. A suggestion that has been made is to assist these users by employing "color coding" on key parts of our UI, so they can learn colors rather than learning the position or shapes of icons or words. We would need four colors to do this, and it would be in addition to other cues like labels.

Something like this:

Because our users are primarily male, it seems especially important to use colors that will not cause difficulties for color blind users.

Palettes developed for color blind users seem concerned only that each color can be seen as different. This is useful in charts and infographics, because a key or legend can always indicate the meaning of each colour. Such as this palette by Martin Krzywinski, uses only colours that don't appear identical to color blind users.

However, since our users will be given instructions like "select the green one", I wonder if this could cause confusion because, even though a CB user can tell the "purple" and "green" palette colors are different, they seem to differ primarily by lightness and could easily be described by either name.

To clarify this point, I made the image below. The larger circles are colors taken directly from Krzywinski's palette, and the small circles are examples of non-palette colors I have made that could be described with the same name.

From a CB perspective (bottom row), the questions "is this purple?" and "could this be blue-green?" seem impossible to answer with certainty.

Are there any ways to work around this ambiguity problem? Or is this color coding approach unhelpful for color blind users?