outlook 2010 on exchange 2010 disconnect message

A couple of things to check - can you ping the exchange server by name, are they using DHCP to pick up correct network addresses if not try changing them to DHCP.
If you hold down the control key and right click the Outlook icon by the clock 2 extra command lines appear 'connection status' and 'test email auto configuration' what results do these give you?

Hello, Both users can ping the exchange server.  Also, both users are receiving these errors: cannot open your default e-mail folders.  you must connect to microsoft exchange with the current profile before you can synchronize your folders with your Outlook data file (.ost).  I have tried adding a new profile and still receive the same message.  I have tried removing 'cached mode' and it errors out right away with a message that they cannot connect to the exchange server.

Also, we're running the connect status test right now.  I'll add those results very soon.  Both users connect using dhcp.

Just a though but I have seen this before try testing with windows firewall disabled

i could not attach screen shots due to the privacy policy.  So hope this helps.
'test email auto configuration': using autodiscover box checked: autodiscover to the exchange server was successful.
'connection status': connecting to casarray.domain - status is connecting - then we receive a disconnect and so we can select reconnect in the connection status box.  but it just does that repeatly.

Try running from RUN box outlook.exe /rpcdiag and see where it is failing

I've also heard that a security log being full may also cause this problem

so we're using group policy to enable firewall for all users computers.  These two users can log into another computer (with firewall enabled) and can successfully connect to exchange and receive email.