I had the same problem - we run four different civi instances.
Two had detailed change logs, two did not.
Across all instances users had same privileges and all four instances had logging enabled. The difference other than civi versions was that two had change log report. So the change log tab runs off reports. Steps to fix:
1) check logging enabled in Misc (Undelete, PDFs, Limits, Logging, Captcha, etc)
2) in Admin > CiviReport > Manage Templates.. check the summary and detailed contact logging templates are enabled (as default they were disabled on ours)
3) The MISSING bit... create an actual Contact Logging Report (Summary) from the template.
and that did the trick.
Note: when creating the report clicking 'refresh results' the report failed to load the results - i guess its too large. But save the report anyway and the detailed changes are displayed on the contact record.
Also it does not seem to need the detailed contact change report created only the summary.
Here the documentation that pointed us in the direction of reports to fix the problem https://docs.civicrm.org/sysadmin/en/latest/setup/logging/
The above worked against: v4.6.22 v4.6.4 v4.6.8 v4.7.20