It's not that they see a few colors that no one perceives, it's that for them color is a 4 dimensional space instead of a 3 dimensional one. So it's a whole new world of different colors.
Even though our eyes detect color in 3 dimensional space, that doesn't seem to be how we perceive it. E.g. I can't tell you how much red, green, or blue is in a color, just that it's close to the cluster of colors I recognize as "purple" or "blue" or "orange" or whatever.
You are incorrect about that, and Randall’s drawing is misleading you (it shows the gamut boundary of an RGB cube, rather than the full three-dimensional color space he asked about in his survey).
For people with “normal” trichromatic color vision, the color we perceive when looking at a particular spot does indeed fall into a three dimensional “color space”. You’re right that without careful attention/training it’s hard to state colors in terms of coordinates in terms of cone cell responses directly or color opponent signals (blue–yellow, red–green, white–black). It’s easy to train someone to give reasonably accurate color coordinates in terms of lightness, hue, and chroma, however.
They find that Russian speakers, who have separate words for two shades of blue, can discriminate between those shades of blue something like 50 ms faster than they can discriminate between two shades of blue that fall into the same color word category.
First thing to note, that's a very small difference.
Second thing: the effect goes away under verbal interference (like when you have the subjects repeat a word over and over again while doing the color discrimination task). So I guess there's an effect of language on color perception, but not while you're talking? It definitely doesn't seem to me that the colors I am perceiving change when I am talking vs. when I am not.
Third, there's a huge overall reaction time difference between the Russian and English speakers in the paper, which calls into question how well the experiment was really run.
So it's not clear that there really are effects of culture/language on color perception; and if they do exist they are very small. (At least that's the conclusion I would draw from this paper, which is widely cited in that field. I'd be interested to hear of different results if they're out there.)
We seem to perceive it in something closer to hsl space (3d) than rgb space (also 3d). You can tell that it's "purple" but you can also tell whether it's saturated or not, and if it's bright or dark purple. Also check out Lab space: http://en.wikipedia.org/wiki/Lab_color_space