Welche Firewall ist denn jetzt neu und welche alt?
Es gibt einige Probleme, wenn man ne neue Firewall installiert, denn meistens bleiben irgendwo Einstellungen der alten Firewall übrig. Sei es als Registry Eintrag oder als Datei. Daher würde ich auch im Registrierungs-Editor nachschauen, ob es noch Einträge gibt. Dann bleiden einige Firewall, die man deinstalliert, trotzdem aktiv. Auch mal in der msconfig nachschauen, ob dort Einträge der alten Firewall enthalten sind.
Auch mal schauen, ob der Ordner der alten Firewall restlos entfernt worden ist.