Errors:
Microsoft.TeamFoundation.Server.WarehouseException: TF221122: An error occurred running job Full Analysis Database Sync for team project collection or Team Foundation server TEAM FOUNDATION.
Microsoft.TeamFoundation.Server.WarehouseException: Failed to Process Analysis Database 'Tfs_Analysis'.
System.SystemException: The trust relationship between the primary domain and the trusted domain failed.
Explanation
Analysis Database Sync failed all of a sudden stating "The trust relationship between the primary domain and the trusted domain failed". The domain trust was fine.
Soultion
1. open Microsoft SQL Server Management Studio
2. Connect to TFS Analysis Service
3. Expand Analysis Service Server name --> Database --> Tfs_Analysis --> Roles
4. Double click on TfsWarehouseAdministrator --> Membership
5. Remove the invalid Ids (In my case I removed the SID ids displayed in the users list)
6. Repeat step 4 and 5 for TfsWarehouseDataReaders
7. open Microsoft SQL Server Management Studio
8. Connect to TFS Warehouse database
9. Expand Tfs_Warehouse database --> Security --> Roles --> Database Roles
10. Double click on TfsWarehouseAdministrator
11. Remove the invalid Ids (In my case I removed the non domain ID which was not related to TFS.)
12. Start the sync again. Open http://<Server Name>:8080/tfs/TeamFoundation/Administration/v3.0/WarehouseControlService.asmx
13. Click on ProcessAnalysisDatabase link
14. Invoke Full sync
15. Full sync should succeed :)