It comes up everytime a website takes a long time to load, it says it only comes up when a website name is mistyped, but it comes up all the time on certain websites. I removed something from the computer from the add/remove programmes menu, but its still there, albeit in a slightly different look.
I’ve tried using Spybot, is there anything else to try?
PerfectNav is a piece of spyware that comes with Kazaa. If you remove PerfectNav, Kazaa won’t work anymore. Do you still wish to remove it?
If you want something else to try there is Ad-Aware www.lavasoftusa.com will have mirrors for downloading of it but remember what Fear Itself said.
Meh, sick of Kazaa as well, they’re both going 
[Please use the following advice at your own risk]
Get rid of Kazaa first, it may get rid of the traces of PerfectNav as well. Actually, you should probably reinstall PN, so that it’s a clean install. Then the Kazaa unistall may find it better and remove it. It’s strange, but if the unistall doesn’t find PerfectNav, it may not try to unstall it, if that makes sense.
If that fails, you would probably have to take it out of the Windows registry. IE is basically a part of Windows, not a standalone application, so you can’t even uninstall IE and reinstall it. Which sucks, and one of many reasons I’m using Mozilla Firefox as my browser and avoid IE if I can - if you break IE, it’s very difficult to fix it. One of my software projects required a specific version of IE - if you upgraded it accidently, the only solution was to reinstall Windows. Unbelievable.
After backing up your registry, you could try to find traces of PN in there and removing them. If you don’t know what I’m talking about, you probably shouldn’t do this, since you can seriously screw up Windows if you delete too much. Otherwise, try Ad-aware like BigDaiv said - it’s an amazing tool. It may find other spyware that you didn’t even know about.
In that case, try Kazaabegone, a free program that removes Kazaa and all assocoated files and spyware.