Actually, based on my reading of the paper, it seems that they learn a representation using one data set (the one with 1000 labeled samples per identity), then use that representation to classify on other training sets (like the Labeled Faces in the Wild, which has 13,323 photos of 5,749 celebrities). In fact, from what I can tell from section 5.1, they seemed to use face pairs (and so trained on 1 sample per person, and then tested on the other sample).

tl;dr: They don't need 1,000 labeled samples per identity (once done with the representation phase), and they achieved 97.25% accuracy on ~6,000 distinct identities, with only one training photo per identity.