There's a less well known counterpoint that illuminates the psychology here. Consider 23 people of the same gender and roughly the same age: what is the probability that some two have the same first name?
Our experience from school classmates etc is that this is quite likely -- most people would guess a more than 50% chance. What does math say?
Well it depends on your culture, so let's say we're looking at 23 year old U.S. women. There is very good data on baby girl names in 1997, and a calculation with the data in this particular case happens to give the same "about 50% chance" as in the birthday problem. (Diversity of baby names has steadily increased over the last 3 generations; for older women the chance would be larger).
Why is our intuition wrong in opposite directions in the two contexts, birthdays and first names? The answer (I guess) is simple: we are familiar with our classmates names and we recall the times there was a coincidence and forget the times there wasn't. But we're not familiar with all their birthdays and simply don't notice those coincidences.