This bug has reappeared and I have investigated its conditions further. The
conditions appear to be the following:
 - Emacs is started with a working directory with only ASCII characters in
the path (no accented letters)
 - There is at least one "multi-file package" in ~/.emacs.d/elpa/
This latter requirement is satisfied even with an empty package (only a
"foo" folder with a foo-pkg.el containing only the necessary define-package
and nothing else.)