You need more insulation than you'd expect. The coldest campsites I've ever had have all been on sand.

Since we're talking about stone age tech, would mammoth pelt offer good insulation?