This post was updated February 17, 2015 with the addition of more turtle taxa to the large reptile tree and these clarified relationships.
Yesterday we opened the door to a new chapter in turtle research by introducing Elginia, known from a horned skull with teeth, as a sister to Meiolania, the horned toothless turtle.
Earlier the large reptile tree nested the large Early Permian millerettid, Stephanospondylus, as a turtle ancestor. And it remains so, just a little more distantly related now (Fig. 1).

Adding Chelonia and Meiolania to the large reptile tree and changing a few character scores with a new understanding of turtle skull morphology changes the tree topology slightly.
As before Stephanospondylus is still basal to pareiasaurs and turtles (Fig. 1). Now the horned pareiasaurs, Elginia and Sclerosaurus (Fig. 2) nest as a turtle and as a pre-turtle respectively.
One of the problems we’ve had in turtle ancestry research may be the traditional misidentification of several turtle skull bones. With the present family tree, however, the homologies become more clear. Here (Fig. 2) is an alligator snapping turtle (Macrochelys temminckii) skull from the Udo Savalli, Arizona State U. website with traditional bone labels.

With the new understanding of turtle bone homologies here (Fig. 3) are the alternate labels. The large changes include: the old squamosal is the new supratemporal; the old quadratojugal is the new squamosal, the postfrontals are not fused to the postorbitals; the prefrontals are not fused to the nasals; the frontals are fused and tiny, much smaller than the parietals; and the tabulars are retained on the dorsal surface of the skull.