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.)