Note: this was on a Windows 7 64bit system.
I've been fighting this problem now for several days. I've been trying to remove and reinstall NIS and the Norton Removal Tool kept saying that I needed to uninstall Norton Utilities 15.
Well, I went into Control Panel and uninstalled NU 15 and restarted and still got the same error when running NRT. After several days of fighting this and searching here and other places on the net for a solution I got so frustrated that I took a SWAG that NRT was seeing a ghost.
I started RegEdit and did a search of the entire registry for "Norton Utilities 15" and lo and behold found two instances of keys with that name. Both keys had no data other than (default). I deleted both of them and their sub keys and restarted Windows.
NRT ran without a hitch!!!!