You are right to be skeptical. The story as it appeared in the media is more or less a fabrication. Here are a couple of good Language Log posts on the subject:
Himba color perceptionIt's not easy seeing greenThe posts are kind of long and technical, but here's the short version. Linguists have found that there is a pretty predictable pattern to the development of what they call basic color terms. In English, these are words like red, yellow, blue, black, white, pink, and so on. We may have names for more specific shades of those colors, but those are the umbrella terms. Maroon is a shade of red, lemon is a shade of yellow, and so on.
There are some languages that only have two basic color terms, which basically mean cool/dark/black and warm/light/white. If a language gets a third, it'll be red, the fourth and fifth are yellow and green in either order, the sixth is blue, the seventh is brown, and then after that we get terms like purple, pink, grey, and orange. (Some people have apparently questioned the universality of this order, but we'll just go with it for now.)
So first off, blue isn't even the last color to be named. Second, there's a big difference between having a word for a particular thing and being able to perceive or conceive of a thing. People who don't have a basic color term for blue can still
see blue, but they might be slightly slower at picking out the blue than people who do have a basic color term for blue. (For the record, the picture of the "test" that the Himba people were given is apparently a fake.) The real tests that I've seen haven't been nearly so exaggerated, and the difference is one of speed, not of ability.
If you take this to its logical conclusion, then no English speaker should be able to see the difference between light blue and dark blue, or between any two different shades of blue, really. Greek has separate words for light blue and dark blue, so obviously they can see the difference while English speakers literally can't, right?
And if you're talking about the physical ability to see color, then you're basically arguing that this is a relatively recent development in human evolution. But how would you explain different groups of humans across the globe evolving the ability to see different wavelengths tens of thousands of years after humans left Africa? And why would that evolution seem to go hand in hand with the degree of advancement that a civilization attains? Because obviously it has nothing to do with the evolution of a physical ability.
As for words for blue going back thousands of years, unfortunately I don't know much beyond Indo-European linguistics. I do know that Proto-Indo-European had words for red and yellow and maybe a few others, but there was apparently no common word for blue, which is why all the different branches of Indo-European have unrelated words for it. Some of those words probably go back at least two or three thousand years. But I really don't know anything about ancient Egyptian, which they mention in the video, or any other ancient languages. But, again, even if no language had a basic color term for blue five thousand years ago, that wouldn't mean that people were literally unable to perceive the color blue.