No log On Server Available With Trusts

We have a complete trust model in a NT 4 network. There are 6 domains. Four of the domains are fine, but when trying to browse the other two domains or connect to a PC from another domain the error “No Log On server is available” is recieved.
All PDC’s and domains have correct LMHOSTS entries.
Using domain monitor from the reskit the two domains that are unreachable show ‘PDC Not Found’.

Anyone have any idea how to fix this.