I always recommend a windows reformat when you change AV's, especially if one was Norton. Norton is nearly impossible to fully remove from your system, and personally, I hate Norton. Its just not a very good product. You should never have more than one AV on your system unless you are very knowledgable in the field...
As for your software firewall, it should be fine.. I will admit I think software firewalls are lousy (Hardware firewalls are cheaper, and more effective for inbound attacks), they seem to be popular for some reason. If you seek outbound protection, theres plenty of non-firewall applications out there that offer that. But thats going off topic a bit too much.