Thought about it, and have no reason to feel concern. In the worst case, the expression "plenty of fish [in the sea]" was around long before the Intertubes, let alone the PoF website.
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.