At least some Neandertals had red hair. According to the story:

An analysis of the DNA revealed that the ancient hominids carried a mutation in the MC1R gene that codes for a protein involved in the production of melanin -- a substance that gives skin its color and also protects skin against ultraviolet light.

In modern humans, primarily of European descent, mutations in the MC1R gene are thought to be responsible for red hair and pale skin by dampening the activity of the protein.

This lends credence to the idea that skin and hair color variations are older than modern humans, which makes sense.