I read a recent article in the Times suggesting the diversity of hair colour arose some 10,000 years ago and that blonde hair was a selective advantage for women. I have gone to the original scientific publication (Evolution and Human Behavior, Volume 27, Issue 2, Pages 85-168, March 2006) because I was intrigued at how they measured that this trait arose prior to 10,000 years ago. Essentially, it seems that sexual selection must have played a role in Europe as humans moved further north 35,000 years ago. The women became more reliant on the men for food and men having to hunt further away from home were more likely to die probably resulting in a higher proportion of females competing for the males attention, thus colourful hair being an advantageous attention-seeking trait.
It turns out that the molecular data gives a rather different date for the origin of the hair colour: "Harding et al. (2000) have investigated this evolutionary scenario and found that the time to the most recent common ancestral hair color would be about a million years, with the redhead alleles alone being approximately 80,000 years old. Templeton (2002) has come to a similar conclusion: If the cause were relaxation of selection, the current level of hair-color diversity would have taken 850,000 years to develop."
The more rapid evolution suggested by the anthropologist Frost is a result of positive selection (rather than relaxation of selection being the cause for polymorphism in hair colour).