Was this a migration of the existing Active Directory - no other changes in the domain or users - or did someone set up a new AD just giving you the same login names?
I ask this because from your description, it sounds like Cognos was configured to point to a new active directory rather than a migrated one. Thus, Cognos thinks the users are somebody different than what it currently has in the permission lists. If this is the case, I think you may have no choice but to reset the permissions.