Hopefully, I'm not misrepresenting the episode. I was listening to it on the way to work this morning. Is blue the "newest" color word? The episode did mention that this is possibly because blue is so rarely found in nature, but it's crazy to think that by the time Homer was writing there still wasn't a word for it.
Should probably also add that they started off by talking about William Gladstone.
You're not misrepresenting the episode, but I'd take that one with a whole shaker of salt, personally. People like to make big claims about what the presence or absence of words in a language means about its speakers. And it's true that language can affect how you group and remember things, but the effects are often overstated (see, for example, this discussion of a similar case here and here). One interesting suggestion I've run across is that Homer and his contemporaries were just more into describing qualities of lighting rather than color: A Winelike Sea
Moreover, ancient Greek did have blue words, such as kyanos/kuanos which meant a dark-blue substance, and eventually came to be used as an adjective for blue (it's where we get the word cyan from). Homer was probably just being poetic with the whole wine-dark sea thing, really.
And blue is found in nature all the time (the sky, water reflecting the sky, certain flowers and fruits, various fish and birds and reptiles, the blood of some crustaceans and bugs, etc), so I'm really not sure how they can make that claim with a straight face. People just talk about it in different ways, as needed. As /u/nlcund says [EDIT: a source for more information about color words across languages], lots of languages still don't distinguish blue/green or blue/black. That doesn't mean the speakers actually see all shades of blue and green as identical. I mean, you can tell all these apart even if you'd call them all green.
But to answer your question as it relates to English, at least:
Proto-Indo-European (maybe 3500 BC, but hard to say) had the root bhel-, meaning shining/flashing/burning/bright, and extended from that something like bhlē-wo‑ meaning blue.
Proto-Germanic (starting around 500 BC) seems to have had a word like blēwaz, meaning blue or dark blue/black.
Old English (starting around 400 AD) did have blāw, meaning blue. It more commonly used hæwen, meaning blue-grey, but it's not one we kept into Modern English. We basically ended up borrowing from Old French (blo, meaning light colored, blond, light blue-grey) instead, for whatever reason. See here for more discussion. Still, we definitely had words for Blue in Old English.
Then Middle English had blewe (spellings varied), and from there we get to Modern English's blue.
Some etymology sources:
Hi, you may be interested in a few earlier comments on Ancient Greek words for blue
