The joke here is that average, to a statistician, means mean—but average, to, well, an average person, means something more like typical. Ted Turner's presence in the bar raises the mean income of the drinkers quite a lot, but the median hardly at all. And when we ask questions about sexual behavior, it's usually typical men and women we want to know about—not averages that can be dragged upward by a few hypothetical Ted Turners of sex.
Not that Kolata's conclusion is inaccurate. As she points out, "Another study, by British researchers, stated that men had 12.7 heterosexual partners in their lifetimes and women had 6.5." These numbers, though Kolata doesn't say so, are means, not medians. In this case, it's indeed mathematically impossible that the numbers are correct. The medians in the British sample? Seven and four, same as in the American study—so you can stop worrying about a transatlantic promiscuity gap. Note that the means are indeed a lot higher than the medians, suggesting that a certain amount of sexual Ted Turnerism is taking place. Since it's as prevalent among men as women, however, it doesn't create the mysterious gender discrepancy.
So what does? One possibility, as Kolata points out, is that people are drawing sexual partners from outside the sample. One hetero Lothario in the next village over could single-handedly increase the median number of sexual partners for village women without (directly) affecting the sexual fortunes of the men. In the CDC study, these outsiders might be prostitutes, or people outside the study's 20 to 59 age range. (Though one imagines there's as much sexual contact between male twentysomethings and female teens as between middle-aged women and sexagenarian men, so this might be a wash.) Kolata observes, too, that people simply might not be telling researchers the truth about their sexual lives. The importance of inaccurate self-reporting is emphasized in the two most thorough papers on the topic I could find, a 1996 article by Wadsworth et al. in the Journal of the Royal Statistical Society and Michael Wiederman's 1997 article from the Journal of Sex Research. Wiederman considers all the explanations I could think of (and plenty more) for the impossible discrepancy of means, and concludes that the culprit is inaccurate self-reporting. One tip-off: The discrepancy shrinks somewhat if you ask people only about the number of partners they've had in the last five years, and even more if you restrict the questioning to the last year, which strongly suggests that unreliable memory is playing a part.
In the end, then, Kolata is right. Studies that report these numbers should emphasize that the reported difference between men and women is an anomaly that can't be taken at face value. But in making this subtle mathematical point, she chose to gloss over a much simpler one—that the mean and median are not the same. The mean is easier to analyze mathematically. But if you want to know how you measure up to the typical American's sex life, it's the median you're after.