It happens to most people. Very few ideas are unique. In fact most aren't.
I'm also looking to avoid legal problems.
Is your product/service classed as competition or do they provide a product/service that's copyrighted?
It would be like me creating a website called ScrewMyLife and finding out that FMYLife already exists. The only difference is that FMYLife is wildly popular and all clones automatically fail. My competitor has probably received a couple hundred thousand visits (the content is very viral), but not enough that a well designed website could easily crush it.