Lost trust issue

Hi

We have a confusing problem.

I lost my trust connection with a partner domain, apparently
when they upgraded their server. (This is all WS2003).
When I try to validate (or establish a trust) I get a message that
"Windows cannot find a domain controller for the xyz domain.
Verify that a DC is available and then try again." When I use
netdom to ask for a DC it says "The specified domain either
does not exist or could not be contacted."

Simultaneously (as far as we can tell) we lost DNS zone transfers
at the same time. Now I cannot get DNS to recognize the foreign
zone. All I get is a notice that "The DNS server encountered a
problem while attempting to load the zone." I don't get anything
in the event log even when I crank the logging up to all events.

The most confusing part of this is that we each have a trust with
the same other domain that seems to be working normally.

What could be going on and what should we look at doing to fix this?

Thanks.

Steve