Surprised you are having such a big issue with this.
Personally, I have the Firewall turned off. If I was worried about internet issues I would actually use
LittleSnitch rather than the built in Firewall. In fact in my previous mbp I WAS using LittleSnitch in conjunction with Control:Mac with no issue. My current machine is pretty new and I havent gotten around to installing it yet.
Another thing I would try, because it wont do any harm anyway.
Run "Disk Utility", select the disk and click on Repair Disk Permission.
Cheers
Greg