'Trusted domain object not found' is about the trust itself.
user you are looking it up against a server that is either trust
controller or trust agent?
Its just this one user. Other users in the trusted domain are OK and the
trust has been up and running without issue for months.
If it is a trust agent, does it have ipa-server-trust-ad package