In one of his latest books, "Next", Michael Crichton makes a quite funny (and sarcastic) speculation regarding this idea of red haired neanderthals and that old urban legend about the inevitable extinction of red hair in current times.  
 
BTW, the book is an uncompromised, entertaining must-read for anyone interested on the subjects discussed in GNXP. 
 
Regarding the books from Jean Auel: there's only one black-skinned character in the book, and he's not native of Europe - he came from Africa, in a long, long trip.