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
(I apologize if this is a duplicate. I tried to post on Sept 3 but it hasn't
shown up.)