This issue seems to be related with the selected field in the search form. Indeed, when you select “men” in the search form, all the users searching a men are visible (men and women included). To solve this issue, you have to make sure you selected the ‘I am a” field and rename it, not the “I’m looking for” field.
However, I’m glad to read you’ve been able to solve this. 🙂