The need more than a changelog, they need some semblance of version control as well. My feeling is that theme version numbers should be matched to the highest wordpress version that they actively support (ie, have been tested for). So most themes now should be 4.2.xxxxx, where the .xxxxx incremental is the only part of the version number controlled by the developer. The rest should be automated in some manner. Perhaps even tie the version number to a changelog system, where the developer explains the change and wordpress assigns the version number to match.

It would make it much easier to search through themes to find the ones that are actually updated and current, and not out of date. So many themes are just not maintained.