Error creating external trust in Windows Server 2003

Active Directory Domains and Trusts wizard error:

The trust relationship cannot be created because the following error occurred:
The operation failed. The error is: This operation can not be performed on
the current domain.

nltest and netdiag do not report any errors. DNS looks ok. I get the same
error in domain A and B when trying to create the external trust. Both
domains are at 2003 domain/forest functional level.