Exchange Instant Messaging can’t connect

I have just implemented Exchange Instant Messaging, everything is working fine except for a few machines. What is happing is they are being disconnected and most cannot reconnect unless they reboot. One person cannot reconnect at all after he gets disconnected from Instant Messaging. The error message everyone that has this problem gets is “Signing in to Microsoft Exchange Instant Messaging failed because of a problem connecting to the service.” has anyone else seen this error? I can’t seem to find any information about this in any Microsoft Resource. They can all connect to the Exchange server without any problems at all.

Any help is appreciated.

Bill