I am in a similar position as you in respect of Norton Internet Security 2006. It has been a nightmare as the e-mail helpline are obviously based in another country and seem at a complete loss to comprehend and resolve the problem despite supplying them with every detail.
I had the problem for three weeks unintstalling and reinstalling in the precise manner as dictated by Symantec. I finally ditched NIS 2006 and installed Norton Personal Firewall 2006. Would you believe it - the same problems there as well. I now give up on Norton/Symantec despite using their products for many years.
Looking through other threads on the subject of internet security it would seem that a firewall is not deemed necessary if one uses ones common sense. I would ask as the interpretation of common sense? What should one avoid doing?