Exchange Server is unavailble

I have a brand new server with Exchange 2000 sp3 and Windows 2000 sp4 on it and 10 of my users can connect and open Outlook perfectly. I have 2 users when they go into Outlook they get the Exchange Server is unavailable and you can hit retry or work offline. I hit retry and you can get into Outlook. How can I fix this easly. I have tried adding a host file to the machine and that does not help. The weird is if I hit retry it goes in and I can work in Outllok perfectly. Any help would be great.