I am a bit sick of seeing the "SOLVED" label with an overly complex solution (bad) or a vague/speculative solution (enough said).
So here is what I have (roughly): Windows 7 & NIS 2013 (v20.0.4.40).
Started getting the dreaded "Error 8506, 421" alarm, followed by an endless (and fruitless) attempt to repair. When I canceled out, it would just start up again five minutes later.
*** Here is the solution that worked for me! *** Make sure the "Norton Internet Security" folder is in the root directory of your start menu. Specifically the following folder must exist: "C:\ProgramData\Microsoft\Windows\Start Menu\Programs\Norton Internet Security".
That's it. I'm not sure if you need all of the programs to be there for this to work, but they are there in my version of the fix.
I like a nice, clean menu structure, so I move the NIS menus (and everything else) to a subdirectory to keep things structured. Several years ago, whatever Norton products (covering a span of 5+ years) I had FAILED TO START if you moved the directory outside of the top of the start menu tree. I was happy when I discovered this was not a problem with NIS 2010, 2011, and 2012 (and maybe a few versions earlier). Apparently, our friends at Norton have decided (perhaps inadvertently) to reintroduce this feature.
Two notes. First, the NIS start menu program is now present - but "hidden" - at the top of my menu structure. No problems for over a week. Second, it seems to me that the only thing that the only thing accomplished by the "official Norton solution" (Norton Removal Tool --> Norton Power Eraser --> Reinstall) is putting the NIS menu back where it needs to be.
I can't say this will work for everyone, but it did work for me. Good luck!