BBCnews is carrying this article summarizing the latest attempt at retrieving DNA information from human fossils. Scientists were able to retrieve DNA from a 100,000 year-old Neandertal fossil, the oldest human DNA recovered to-date. The findings reveal Neandertals were more diverse earlier in their history, suggesting fluctuations in the population perhaps caused by disease or environmental change.

In other words, if I'm reading this right, one interpretation is that Neandertals suffered from some sort of disease or environmental change which caused a significant decrease in their numbers. They may have already been on their way out when we showed up.