Hey Stephen,
I about pulled my hair out with this same problem. I had NAV 2004, and trying to get rid of that and install NIS 2005. I did the clean boot and followed every direction to the T...Ha! I finally went to the keys and had to remove any key that had to do with Norton or Symantec, and then it worked. You also have to do an update right then for it to start working. I did not have any problem with my add/remove, sorry I cannt help any there. Symantec needs to really work on their add/remove program because it doesnt do the trick! I had to contact microsoft and reactive my windows due to so many attempts...I thought "OH NO!" Good luck, I hope this helps you maybe, and any one else that reads this. wizmom_00