I can't get that link to work, but there could be your answer, JK, thanks to Dack.
As this problem only seems to affect the Firewall, the best idea might be to change Firewalls, at least until the problem is sorted out. I'm very surprised that this has been ongoing since 12th May, without Symantec issuing a further update to repair things. Lona suggested Zone Alarm, and I suggested Sygate. Take your pick.
Once you have uninstalled Norton Firewall, check your definitions in Anti-Virus again, and if they have not re-appeared, try re-installing NAV. Make sure you do as much of this as possible, offline, so as not to put your system to uneccessary risk. You will have to uninstall Norton Firewall before installing an alternative.
Edit: Link working now.