Outlook 2K on Win98 w/Exchange 2003

I'm having issues getting some win98se machines accessing Exchange 2003 with Outlook 2000. We've installed (on the 98 machines) the office updates through SP3 and have installed DNSClient and set the suggested registry settings. But will can not get passed the authentication to the Exchange server. We also have a web interface to the exchange server and the same users that can't authenticate through outlook can log on to the Web interface without any problems.

Any Ideas?