Exchange haywire!

I have recently had a problem with my exchange 2000 server, running on Win2k server with Active Directory. The problem is that the clients would take ages to log into exchange, outlook would just freeze, and then finally log in.
I ran service pack 3 for windowns and for exchange 2k Server.
After the Exchange server came back up the users are not able to log in at all… the long pause is still there and when outlook finally responds it is coming up with a login box. asking for name, domain and password. the login however is not the network login as it comes up with an invalid login message whenever any network user or admin tries to log in.
ANy help that you can give would be gratefully received!!!