1. Contamination with other flora and fauna DNA 2. Relative low proportions of human DNA 3. The DNA is usually highly degraded, which limits the analyses to short read sequencing (in this case they used 76 bp reads). The halflife of human DNA is ~521 years.
To mitigate these problems they used multiple targeted approaches including one to isolate mitochondrial DNA, where they managed to sequence the whole ~16kb human mtDNA, where each base was covered by 62 sequencing reads on average (62x coverage).
They used another to isolate specific regions containing single nucleotide polymorphisms (SNPs), which are DNA mismatches known to be related to ancient human DNA and humans. They targeted 470,724 single nucleotide polymorphisms of which 70% (336,429) were recovered.
They did perform shotgun sequencing on all of the DNA isolated, but due to species assignment issues they again focused on fragments that contain diagnostic SNPs in these cases they only recovered a small number of SNPs per sample, again due to the relatively low proportion of human DNA and its degradation (20,526, 3,734, 124,862, 85,901, 34,756, 41,632, 34,677 and 72,992) as per the legend in figure 3.