I don't think you can make that conclusion.

I think you're making the assumption that all three data points are needed for all 87%. But obviously some people can be uniquely identified based on just {zip, date or birth}, such that gender isn't necessary.

So the distribution could e.g. be 8% same, 8% opposite, 5% both, 79% neither, and explain the original numbers without triggering the paradox.

Yeah I was off, but by their numbers

87% of the time, there are no others on my birthdate or there is one other and opposite gender.

13% of the time is 1 same gender or more of either or both.