The confusion arises because of the difference between what you mean when you say “men have, on average, more sex partners than women” and what the surveys show which is that “most men have more sex partners than most women” or “men typically have more sex partners than do women.”
Considering only heterosexual partnerships, the total number of sex partnerships formed by all the men in the world must equal the total number of sex partnerships formed by all the women in the world so the statement “men have, on average, more sex partners than women” can’t be true if we are talking about the entire universe of sexually active persons. However, sex surveys only sample a portion of the universe and they usually focus either on the “general population,” some subset of the “general population” (e.g., sailors, 15-19 year old girls, etc.) or prostitutes. They don’t even attempt to get an unbiased sample of the total population because if they did, the data from prostitutes, who are at an extreme in terms of numbers of sex partners per unit time, would throw off all their averages unless the prostitutes were represented in the sample precisely in proportion to their proportion in the total population. (Example: you sample 500 people of which 50 have 0 sex partners, 250 have 1, 100 have 2, 50 have 3 and the remaining 50 have an average of 5. This averages out to 1.7 partners per person. Now what happens if you include just one very busy prostitute in your sample. Now your most promiscuous 50 are 49 people averaging 5 partners and one person averaging 500 partners. Now the average number of sex partners for the people in your sample is not 1.7 but 2.7! Take home lesson: sampling is important.) You could, of course, include prostitutes in proportion to the proportion of prostitutes in the total population if you knew what that proportion was, but you don’t.
So when people study the “general population” and find that “men have, on average, more sex partners than women” they are under sampling prostitutes. The important thing that they usually find is that it is that the proportion of men who have few (less than 2 per year or less than 3 - 5 lifetime) sex partners is lower than the proportion of women reporting so few partners.
All this points out how dangerous it can be to use measures such “averages” to describe differences between populations. More meaningful in this case is the median. The median number of sex partners for men is higher than the median for women. Better yet, when comparing numbers of sex partners reported by men and women, one should report the proportion of each sex with 0, 1, 2, 3-5, 5-10, and over 10 sex partners (or some similar breakdown) to really get a good picture of the male-female difference.
And yes, men tend to exaggerate and women tend to minimize. Anyone doing sex behavior surveys knows this and takes it into account.