The thing I miss in most changelogs is that they often discuss what changed, while you can see that by looking at the patch. What you want is *why* it was changed. What is performance, a bug, a feature, some forgotten corner case, or something else?
The entries that bug me the most: "Refactor code XYZ" (sometimes with more words, but the result is the same). Completely useless, since it doesn't explain what was wrong with the old way or why the new way is better.