As a business owner not a lawyer my response to this kind of thing is always to consult my lawyer. The question isn't necessarily "does it infringe" but rather "how best to proceed," and it will take an actual conversation between you and your lawyer to figure that out together.

If'n you don't have a lawyer, asking others if they know somebody who does "startup stuff" is a good way to dig up recommendations for the kind of help you'll need, which you do need now and will likely need in the future.

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).

You should change it to: Go Fish.. or GoFish.

I don't think your clear statement means anything, legally. What matters is the name similarity. If a soda company was called Pepsee and then stated, "We are not Pepsi, a registered trademark of the Pepsicola Corporation", they would still get sued into oblivion.

IANAL, but it strikes me as at least arguable as "confusing similarity" (http://en.wikipedia.org/wiki/Confusing_similarity). Do you want to find out the answer in court, or could you just change the name of your app to something obviously different from "plenty of fish"? Like "The Gorton Fisherman of Love". No, don't do that.

(I'm curious if there is any additional concern about making a client for something without permission)

OP Update: They issued a take down request to Microsoft, which required they fill out a form on specific infringement of the app. I'm actually glad they did this, as Microsoft has a formal process for reinstatement of Windows 8 apps that previously may have infringed, and this way I have a list of things they want changed without having to officially be on the record communicating with them directly (where they could use anything I write against me).

Complaints: They have copied the POF icon and used it as their own. This application is passing off that it is an Application from Plentyoffish Media. They use our trademark in their description. Also, the word "Many" in title is clearly a play off of "Plenty Of." We have many other trademarks in many other jurisdictions for this and related trademarks.

First off: Breath. Second: Talk to a lawyer.

I panicked receiving my first C&D, but now I'm more experienced and see them less seriously.

See if your lawyer can get in contact with a human at POF to explain the situation.

Edit: Wow, I just read the letter you pasted. It even has typos. Lawyer up. This seems automated or by a lawyer in a hurry who isn't prioritizing this.

"your firm is promoting to the public online dating services under the name ManyFish"

This looks like a boilerplate response, and that phrasing appears to cast your app as a competing service.

Like the others said, you probably either have to try to reach an actual human being at POF, or let the lawyerbots do their dirty, mechanical business.