The 8506 error just appeared on out of the blue after a year of stable operation. I followed the uninstall/reinstall instructions as per Norton's support site repeatedly to no avail. After much, MUCH googling i pieced together a series of steps that worked for me. I hope they'll work for you...I'm on Windows 7 x64 with NIS 2013.
In my case, NIS allowed PUP.Optional.Spigot.A to infect my system. Norton Power Eraser missed it too. i ran MalwareBytes after the 3rd or 4th failed reinstall attempt of NIS. Even after the trojan was removed, NIS STILL didn't work so this is what i did.
1. Install Ccleaner. In addition to the defaults, check the option to remove the "old prefetch data" as well and run it.
2. Manually delete the contents, NOT THE FOLDER, of C:\Windows\Prefetch
3. Go to the Norton support site. Download & run Norton_Removal_Tool.exe. Follow the instructions but DO NOT RESTART when it is done. NOTE: The easiest way to find the norton removal tool is to click the "Open Support Site" button found on the Norton error window.
4. In the run menu, type regedit to open the registry editor. Press the F3 key or got to Edit -> Find to initiate a search. In the search window, just type "Norton". To search for the subsequent Norton registry keys just keep hitting F3. Delete EVERY SINGLE line item with the word Norton in it. You will run into several keys named NIS. Instead of only deleting the subkey data, delete the root of said keys where possible. Some of the keys will NOT delete. This is normal as we haven't restarted yet. This is not for the faint of heart...If you have any qualms about hacking the registry skip this step proceed with the rest. Please report back if it works without hacking up the registry.
5. Now you click the Restart button on the Norton Removal Tool. Once your back in windows, Internet Explorer will auto-open to Norton's site. Make sure you download and save (but DO NOT RUN) the Norton reinstallation app (NISDownloader.exe)
6. [SKIP IF YOU DON'T WANT TO HACK REGISTRY] Once back in Windows, regedit again and do the same search for "Norton". There WILL be a few more norton entries to delete.
7. Reboot again.
8. Delete the two Norton folders --> C:\ProgramData\Norton AND C:\ProgramData\NortonInstaller. If you cannot see the C:\ProgramData folder you must setup windows explorer to show hidden files. Go to Tools -> Folder Options -> View tab or just google a how to.
9. Reboot again
10. Now run the NISDownloader.exe you saved in step 5. It will now actually reinstall the product from scratch this time. When done installing, if Norton claims your trial has run out and you need to activate, you can celebrate! ;) Just activate it like normal and run live update. In my case it even offered to patch itself as well.
I hope this helps. Good luck!