If that's the case and their app predates Who's Near Me, I have to say that the OP is probably going to lose this. The names and apps certainly do seem confusingly similar.
Genuinely curious. Do you think they have owners ship of "who" in the context of a social network. Surely using such an obvious descriptive name should count give you less rights to similar names. IE If I have "The Family Teacup Company" I can't complain about "The Swedish Teacup Company."
The trademark is for the concatenation 'whoshere'. Given that both are common words obvious to the topic I would have thought the interpretation would be very narrow and 'who's near me' is suitably different. I certainly don't think you should give in to their somewhat extortionate demands.
"Red" and "Hat" are common words too, but you'd never get away with trying to sell a linux distro named "Red Cap".