I'm pretty sure in reality Facebook also uses your social network graph to restrict the candidate set and get higher recognition accuracy. This makes it hard to compare Facebook's results to a pure recognition algorithm.

On that note, Facebook could do even better by restricting the candidate set based on time, precise location, and compass orientation, given that most mobile users have Facebook installed and are running it in their pockets when they get their picture taken by others. (They could do rough recognition purely based on position and orientation without even looking at the camera image, if they really wanted to, so with the camera image it could really be near 100% accurate, and even work if you take a picture of a friend's back.)