You should make Neanderthals another PC race. And, "real" neanderthals, none of this
quest for fire stuff where they just bang rocks together. Modern Anthropology suggests that Neanderthals (who, after all, had the largest average brain case among humans) had great ability to focus on a single task, and possibly had the same abilities for symbolism (ie, rituals and art) as homo sapiens sapiens.
Really, ice age is the perfect place for neanderthals, who aren't all that different appearance-wise from modern humans.
Also, I have to agree with the "Keep the gear the same, just change it's name". To me, the real problem is in getting the overly fantastic stuff out. How, for example, do you explain a paladin? Some of those abilities just don't seem to fit in with an ice age flavour.
I like the idea of the previous ruins being tiefling or serpentine in nature. It's a cool idea, very H.P. Lovecraft in a lot of senses. As for Elves and Gnomes being the primary threat, why not make the elves sort of like the Sithi in Tad Williams' Memory, Sorrow, and Thorn series? And gnomes, to make them fearful and cool (flavour-wise), why not have them steal human infants, which they raise as changelings? The stolen humans could slowly change into gnomes, which is how gnomes "reproduce". Makes 'em pretty damn scary.
As for races, humans and half-elves (and possibly Neanderthals) is still pretty slim pickings. Why not add halflings, as they are often lumped in with humanity in core D&D anyways?
Hmmm... you could replace the metal armors with functional equivalents made from the hides of mythical/paleolithic beasts. Maybe they don't have plate armor, but some tribes can fashion the shell of the still-roaming glyptodon into something statistically similar.
Which is another point-- "Stone Age" just refers to the material technology available. You could still have pockets of advanced societies that have developed agriculture, animal husbandry, complex stonework, art, music...
It does sound like fun.
Yeah. "Stone Age" societies wound up getting pretty complex. Much of Mesopotamia, for example, was "Stone Age" (technically, it was Chalcolithic, as it used copper and later bronze). Aztecs were Stone Age, up until the arrival of the Europeans, and they had all sorts of great inventions (law, farming, canals, huge pyramids...)
Really, though, I think the OP is referring to the "Old Stone Age", tied to the ice age hunter/gatherers.