Server 2003 firewall slows logon

The Windows firewall on a Server 2003 domain controller is creating
problems.

It can take 2-3 minutes (or more) to logon & 5 minutes to log off with the
firewall turned on
It takes less than 10 seconds with the firewall turned off

The domain controller is all patched up - as are the Vista workstations.

I have already created more than a dozen recommended exceptions on the
firewall.

I am using the Windows firewall because the McAfee firewall SUDDENLY would
not allow RDP to the domain controller (but does to workstations)