I have a win2k Server in one forest "S" and another in forest "A". 
After much work I am finally able to ping each machine "S" is on
192.168.55.240 and "A" is on 192.1.1.16.  When I try to set up the
trust on A I get:  "The domain can not be contacted. If this domain is
a windows domain the trust cannot be set up until the domain is
contacted."  When I try to set up the trust on S I get: "The security
database on the server does not have a computer account for this
workstation trust relationship" or "Active Directory cannot verify the
trust."  Also there doesn't appear to be any DNS info for forest A on
S or S on A.  I have researched this on MS Knowledge base and it told
me to make sure DNS WINS or LMHost are configured properly.  What
should I be looking for? and What should I do?

First I would like to let you know when you have two forest in Win2K
you can only have bi-directional trust and not transitive trust.

Click the Trusts tab, and then click Add to create both sides of the
trust relationship to the remote domain. Because this would normally
be a Kerberos trust, creating both sides of the trust is required.
Creating the trusted side first generates the following error message:
You would get this error " Active Directory cannot verify the trust.
Access is denied. "

Click OK. Note that Active Directory Domains and Trusts displays the
trust as type "Shortcut" and that it is transitive. Adding the
trusting side generates the following message:

To verify the new trust, you must have permissions to administer
trusts for the domain XXX. Do you want to verify the new trust?

Click Yes, and then supply the administrator credentials for the
remote domain. Whenever you are prompted for credentials, be sure to
specify the domain name as well as the user name, for example,
NetBIOSDomainName\Administrator. The following error message is
generated

Active Directory cannot verify the trust. Access is denied

Click OK. Again, note that Active Directory Domains and Trusts
displays the trust as type "Shortcut" and that it is transitive.

After both sides of the trust relationship have been created, run the
following command.

NOTE: The NETDOM utility is included with the Windows 2000 Support
Tools included in the \Support\Tools folder of your Windows 2000
Server or Professional CD-ROM.

NETDOM TRUST local_domain /Domain:remote_domain /UserD:administrator
/PasswordD:* /UserO:administrator /PasswordO:* /Reset /TwoWay

where "local_domain" is the domain on which the trust is being created
and "remote_domain" is the parent, child, or tree root domain being
trusted. In either case, the fully qualified domain name (FQDN) should
be used. For example, "MyDomain.com". This should result in the
following message:

Type the password associated with the domain user: (This is UserD)
Type the password associated with the object user: (This is UserO)
Resetting the trust passwords between local_domain.com and
remote_domain.com
The trust between local_domain.com and remote_domain.com
has been successfully reset and verified
The command completed successfully.

Reboot the PDC where these changes were made

After rebooting, allow time for the Active Directory to establish a
secure channel and the Knowledge Consistency Checker to attempt to
re-establish replication links to the domain controllers in the remote
domain. During this period, test that logons across the trust
relationship are successful and that the event log errors have ceased

This was the same problem which I was facing, I did the same as above
and it did work.

Let me know if in case you need any further help.

Regards

Buddy, I have the same problem with the trusts.  Completely ignore
what this guy posted. Even though it absolutely accurate, it does not
apply to your situation.  Your issue is one of a couple problems that
I can kinda' explain.

Possibility 1:
  You've made some sort of drastic changes to your firewall and you
can ping from both sides, but you're having trouble sending important
traffic to the necessary ports in order to establish trusts.  Are you
using a IPSEC tunnel?  Are you even using a firewall?

Possibility 2:
  Check your DNS and make sure you have SRV records on both sides for
both domain controllers.  Domain A should have DC A and DC B's SRV
records.  Domain B should have DC A and DC B's SRV records.  Chances
are, and I'd be willing to be the farm on it, the domain controller in
which you can contact the other DC has SRV records and the domain
controller in which you can't contact the other DC doesn't have SRV
Records.

(What are SRV records?)
  Go into DNS and look in the forward lookup zones.  Find the domain
in question.  Expand it.  It should have have the records:
_mcdcs 
_sites 
_tcp 
_udp

These records signify that a Windows 2000 Domain is recognized.

These are two things to consider, even though they don't directly
answer your question.  Suffering from the same problem, I was hoping
that some does in fact answers you question based on the information
I've provided.  Your next best thing would be to remove your question
and call the big wigs at M$.