There are, of course, complications :-)

First, people are not fungible at all (outside of the fairly rare "any hole will do" approach and no, I don't mean bisexuals).

Second, there is a lot of fuzziness about what's actually being traded because under consideration is the whole spectrum from casual one-night stands to till death do us part. Notably when talking about the sex marketplace, what many people want is actually a relationship and that's a bit different.

Third, there are difficulties because what you offer to exchange is not well-defined, partially hidden, and, to top it off, the participants have an incentive to lie about it.

Fourth, as you note, the market isn't quite symmetric in that men and women have different needs, expectations, approaches, and techniques.

All in all, the market certainly isn't perfect, but I don't know if I would characterize the situation as a "market failure". It's just the usual human mess that most manage to muddle through.