Problems logging onto an NT4 domain

I have 4 XP Pro workstations which have been configured to connect to an NT4 domain. The computers have been added to the domain without problems but I am now unable to log onto the domain as a user.
When trying to logon to the domain as administrator, or any other user account, you get an error that the domain controller is unavailable or the computer account could not be found.
When trying to view the computer account from the server you get an error that the PC is not trusted on the domain.
All NT4 workstations will logon without problems but I am getting nowhere with the XP PCs. Any help would be appreciated.