If I have a program X installed that is not part of the list in Control Panel\System and Security\Windows Firewall\Allowed Programs - does that mean it is blocked? If not, when I click on 'Allow another program...' and select X to be included in the list and uncheck the checkbox behind the name - does that mean it is blocked? In any case, I am not able to uncheck the Home/Work (Private) column - why not?
If you use Windows 7, you can check default rules in Windows Firewall with Advanced Security (look for it in windows firewall window -> Advanced settings option). By default all outbound connections are allowed, unless you have blocking rule. For unchecking - can you try to switch network type?