Have you spoken to a trademark/copyright lawyer about any potential infringement and/or brand confusion claims that PlentyOfFish.com will inevitably bring up against you?
It doesn't matter at all that the phrase was in use before. What matters is that you are offering a service that is similar enough to cause confusion. People could reasonably think that you are associated with Plenty Of Fish, because the name is similar and both your services involve internet dating.
I'd seriously consider changing names. They make several million dollars a year and trademark law pretty much requires that they vigorously defend the mark.