Yeah, the Norton Removal Tool is a must when trying to uninstall. Recently I did a restore from disc for a friend, after a couple of hours the restore was complete, the first pre-installed crapware I tackled was Norton/Symantec. Used the uninstaller and then used a registry cleaner. Immediately after that, I tried to get into system restore and got the "rundll as an app" error. Damnit! Had to start over, and then used the NRT tool successfully.
The only things that come close to the difficulty of cleanly uninstalling Norton are some antivir products. But Norton really takes the cake for fooking up the registry. BTW, this tool is from Symantec, in response to numerous complaints. MajorGeeks offers it as well:
http://www.majorgeeks.com/Norton_Rem...NRT_d4749.html