Error Connecting to Exchange 2000 from Outlook the first time

[Mac]

About two weeks ago my users started getting an error
message the when they started up Outlook. The error is:
"Your Microsoft Exchange Server is unavailble." and you
get the Retry or Work Offline buttons. If you hit Retry it
will connect about 45 seconds later.

I made no changes on the server or the users machine
before this problem started.

The Error only happens on windows 98 machines. It just
takes a long time to come up on WS 2000 machines.
I have run all of the eseutil option on the Private and
Public stores and have had no luck.

Any clue what might have started this and how I might fix
it?

Thanks!

Digitally,
Mac