I've found that after trying to remove a firewall there can be hard to find traces of it left behind,and then some new firewalls won't install because they say the old firewall is still there...
Have you gone to Norton's website and looked for a "Removal Tool" for that firewall? Try that.
Go to Windows Search and look for any files or folders for it and delete them. Go to My computer/C files and look for any.
Finally go to regedit again and search for any remaining files you can find,sometimes an incorrect name seach won't show all the files,I would just type in "Norton" and see what you find.
Sometimes you'll find files that "Cannot be removed" in regedit,if these are "Legacy" files they CAN be easily removed,right click on the file,click on permissiions,then check the box "Full Control"(Something like that you'll see).Then go back and remove the file.
Also download Revo uninstaller,it will do much more thorough uninstall when you want to remove programs in the future.
When you're all done run CCleaner to remove any useless remaining crap.