Did you try adding via the various notations? domain\userid userid@domain
Are you sure that the 2-way trust still exists?
What version of TS?
Does the Tableau Server runas account have access to both AD domains?
Go to Manage Product Keys and check your date(s). Refresh if the date(s) is not updated. You have probably crossed a maintenance date and need the server to acknowledge the new key expiration. After refreshing, restart the Tableau server for it to recognize the update.