Fileserver cannot find any DC’s for trusted domain

The problem

Due to a merger in our organisation, we are migrating to a new common Active Directory domain. Our old legacy domain and the new domain have a two-way trust between them.

We have two main fileservers in our old domain, on which users have a personal folder. Some users have their folder on one server, others on the other one, depending on which department they work for. On these personal folders, NTFS permissions are granted using the users account directly.

A user has an account in both the old and the new domain. So now I was in the process of adding permissions to these personal folders for the corresponding user from the new (trusted) domain. Strangely, this works fine on one fileserver but not on the other.

I scripted this in powershell and it throws the following error:

Add-NTFSAccess : Cannot bind parameter 'Account'. Cannot convert value "<New Domain>\<New Username>" to type "Security2.IdentityReference2". Error: "The trust relationship between the primary domain and the trusted domain failed.

When i manually try to add the permission. I can see the other domain as well as check the name of the user. But when I try to apply the permissions I get the following error:

Things I've checked so far

• The DNS names of the DC's of the trusted domain resolve fine from the fileserver
• Verified the trust in the "domains & trusts" mmc (All other trust related things work fine btw)
• The fileservers are in different firewall zones. I asked the network guys to temporarily allow all traffic between the file servers and the DC's of the trusted domain for testing. (But the correct ports should have been open anyway, since the rules are the same for both fileservers)