While a reformat would be a sure way to make sure there is no residue leftover from Norton, you could instead unistall it, delete it's entries in the registry, and the folders it created on the hard drive. That would remove a lot of Norton's mess. A Defrag after that would be nice, prior to installing whatever other Antivirus/firewall program you have.
I've installed Norton Internet Security on other folk's computers, never had any issues with it. Though I definitely do no reccomend it for bargain processors, such as Celeron. Thena gain, I don't reccomend those type of processors at all.
One just has to know how to work with Norton. It's a decent program, however if you don't have all the resources it wants, then it's more the fault of not feeding the program what it needs.
It is a bit more bloated than it needs to be, I have similar feelings about Nero Burning software. Decent stuff, however the new version has a whole lot of stuff, and for what I need it for the program only has to be simple. Nero 7 is a decent program, just more bloated than I care for at the moment. So, I use Padus Disk Juggler, whose new version works just fine with Vista (32 and 64 bit).