Connecting Win98 machines to NT4 Server

When attempting to log on to an NT4 domain from Win98 workstations, users receive error message of “The domain password you supplied is not correct, or access to logon server has been denied.” The PW is correct, and after 3-5 attempts, they are eventually able to log on and access network resources. The workstations have static IP addresses, use WINS for NetBios resolution, have a new 100mbps switch on the network, and no trailing spaces exist within the computer name or after the name. Any ideas as to why this error message is happening. The server and the Win98 workstations are brand new.