Yes, I have to login with a cached account or local account, remove from the domain and then rejoin again. The laptops are set to use DHCP, so should never have issues as they are pointing to the server.

I know what you mean, because there was a case recently where a pc was set using the wrong server and it was taking forever to login and I could not rejoin the domain until I fixed the DNS issues.

No the trust relationship issue seems to be more to be with computer authentication than with DNS.