Mac Clients can’t see Exchange Server

Server:
Exchange 5.5/sp3 on NT4sp6. Also Running proxy, IIS, and Services for Mac.

Clients:
PC – run various outlook versions just fine.

MAC – NOT ONE FREAKIN’ MAC CAN CONNECT.
When I click “Check Name” the machine saids it has problems communicating with the Exchange server. I tried this on Appletalk and TCP/IP. Even went as far as making a host file on a mac. Tested the name via a browser by connecting to the iis. the name works great.

Can anybody help.