IANAL.
Their letter isn't very good writing. Their only stated claim is that the word "ManyFish" infringes their trademarks on "PLENTYOFFISH", "PLENTY OF FISH" or "PLENTY OF". They say they can ask IANA to take your domain, but an app is not a domain. Also, if I understand correctly, your uses of "PlentyOfFish" in the app description are nominative.
However, if they don't like unofficial clients for their website, they can also block you by technical means, and doing so likely puts the law on their side even if it wasn't before (cf. Craigslist/Padmapper/3Taps). So fighting the C&D letter might be pointless, if they care enough about you to follow up on the letter.
Perhaps you could try to contact someone other than Legal at PlentyOfFish and see how they feel about it... sometimes legal departments are more aggressive than the company intends to be (I have no inside info about PlentyOfFish).