Assuming Vista ! but maybe the same problem with xp.
Think your right Wolfman;
Im on Vista and have had the same problem since the last batch of updates and due to the complex way of Vista firewall,its almost impossible to create a group policy rule to allow connection.
However,i sorted mine by;
1) If you have a router Nat firewall enabled,disable this.
2) Unplug the router.
3) Disable Vista's Firewall
4) Reboot the computer
5) Plug the router back in and enable the Nat firewall.
6) Enable Vista's Firewall.
This has sorted mine and i guess Vista has recognised the new settings and all works fine for me.