I had a similar problem. I had something called PC-illin (or something like that) from my brief attempt to get earthlink dsl to work, and I was not able to uninstall it no matter what I tried. But it was preventing me from installing McAfee, which comes free with my cable internet access. Finally I went to the website for the company that makes PC-illin and after poking around a bit I found a link to click to uninstall the software. They had different links depending on what version you were trying to uninstall, and I found one for mine even though it was several years old.

So go to the McAfee site and see if they have any uninstall help there. Also you can try calling their tech support - they might be reluctant to help since you're not a current customer, but maybe they could at least point you to the place on their website where you can get what you need.

Good luck!