Windows (including Exchange 2007) service connectivity problem.

I experienced a communication anomoly yesterday, and have no explanation for it.  Problem solved now after rebooting server; however, I'd like to know the specific cause and a better solution than rebooting the server if I encounter the problem again...

A lot of info to follow, so please consider the environment and all factors before responding.

Environment details relevant to problem.

Branch Office 1:
Juniper SSG5 Firewall connected to DSL for backup and local Internet access
Juniper SSG5 Firewall responsible for DHCP
Juniper SSG5 doubles as backup VPN connection to HQ if MPLS drops offline
Cisco 1811 Router connected to MPLS T1, BGP routing across MPLS
Cisco 1811 is default gateway
Cisco 1811's default gateway is Juniper SSG5
Cisco 1811 has static routes defined to Corporate HQ
Approximately 40 desktops and laptops (all XP) in branch
Primary DNS points to 2003 DC in Corporate HQ
Secondary DNS points to backup DC in Corporate HQ
Terciary DNS points to 4.2.2.1
--Note-- I promoted the branch's 2003 server to a DC yesterday, and it's running DNS, but I haven't updated the DHCP scope to include the local DNS server yet...

Corporate HQ:
Cisco 1811 Router connected to two bonded MPLS t1's, BGP routing across MPLS
Exchange 2007 Server
Exchange 2007 Server connected to Internet via port forwarding from HQ firewall
Exchange 2007's default gateway is HQ firewall
Exchange 2007 Server has static and persistent routes defined to communicate with branch offices
Exchange 2007 Server only accepts inbound connections from internal hosts and Internet Hosted anti-spam servers


Problem + Circumstance:
I replaced the SSG5 in the branch yesterday and shortly thereafter several hosts could not communicate with the Exchange server.
My guess was "it's a DHCP problem" becuase the new SSG5 was doling out addresses now and didn't have the list of assigned addresses from the previous SSG5 (however, I didn't notice any address conflicts.)
Both SSG5's are the same model, firmware rev and had the same configuration

Tests:
I WAS able to ping the Exchange server from the affected hosts "BY IT'S HOSTNAME"
I WAS able to ping the affected hosts from the Exchange server
I cleared the DNS cache on the Exchange Server
I added Exchange server to local hosts file (likely overkill, but I was reaching here...)

I was NOT able to connect to Exchange via outlook, OWA, RDP or network share (logged in as an administrator I tried 'start ->run->\\exchangeserver\c$')  nothing connected
I tried to telnet to exchange server's RDP port (eg. telnet exchangeserver 3389) NOTHING
I performed a tracert to and from Exchange server to verify the correct route path was being used (primary path = MPLS, backup path = VPN over Internet) and confirmed packets in both directions were following the correct path.


After much frustration, I removed the new SSG5 and returned the previous SSG5 to service... still no luck (even after releasing and renewing IP addreses.)
Ultimately I rebooted the Exchange server and all was well.

Oddly, a similar problem occured with connections to my primary DC in HQ (which behaved correctly after rebooting as well.)

Note - I WAS able to access Exchange services AFTER rebooting it and BEFORE rebooting the DC.
Note - I WAS always able to ping to and from the Exchange server to the affected clients when the Exchange services weren't available.

Thoughts?

I know that was a lot of information to digest...  ;-}~
I will be out of town for approximately 36 hours, so I may not reply until Monday unless my hotel has Internet services available.

Thank you,
FHMC