I'm no IT expert but I'm about to try and solve this issue from the suggested solutions so will feed back if I have any success.
Been having this common problem myself recently - even after several re-installs/using power eraser etc (no viruses or malicious software found) Norton Internet Security is stalling and getting the Microsoft Windows "Norton Internet Security has encountered a problem and needs to close" error message every time on starting up the pc, sometimes repeatedly, or along with 'the system has recovered from a serious error' messages, again sometimes repeatedly. For the first time on loadup today got the Norton Error: "8506,421" message - already tried Norton's suggested fixes several times (removal tool/ power eraser/reinstall) but this does not resolve the issue for me - it keeps failing even if it works for a while.
Norton Internet Security
21.5.0.19
Error: 8506, 421
Microsoft Windows XP
...sp3...
Norton Autofix Results: 0 item(s)
having read the solution suggested below makes me wonder if it is to do with a change to where the product's start menu files are or some other startup or shortcut issue as the time I started getting the issue a new 'live update' icon appeared on the start menu and taskbar, since then the product is frequently closing down with or without an error message or failing to complete updates/checks. Checking the properties of this start menu item it has the target ' C:\Program Files\Norton Internet Security\Engine\21.5.0.19\uiStub.exe" /lu ' all the above are present (not sure what the /lu bit is) but this icon was not on the start menu prior to getting the issue so as feedback I'm wondering if there is a connection if NIS added it, although it may just be Windows pinning it to the Start Menu due to frequent use.
just about to test out this solution - http://community.norton.com/forums/error-8506-421-solution-not-complex as this folder is not present on my system, however my (Windows XP) Start Menu folder is at C:\Documents and Settings\PACKARDBELL\Start Menu\Programs so I'm also trying adding a folder 'Norton Internet Security' there, will restart and see what happens (will then update info here)