I'm a bit dubious about nuking registry entries, is this the way forward? Or is there something else I could possibly try?
Getting rid of those Registry entries referring to both Symantec and Norton (assuming you have no other Symantec siftware loaded) seems to me to be the way to go here.
Warning: Back up your existing Registry first!
http://support.microsoft.com/default.aspx?scid=kb;EN-US;Q256419 gives Microsoft's explanation of how to do this; at the very least, copy the system.dat and user.dat files to a CD or another removable medium (a floppy would do).