I was able to reproduce the problem by uninstalling xfonts-75dpi and xfonts-100dpi.
So another solution might be for nedit to recommend those fonts, as is done in grace (which is the package I happened to have installed on Vivid):
Recommends: xfonts-100dpi | xfonts-75dpi | xfonts-100dpi-transcoded | xfonts-75dpi-transcoded
I was able to reproduce the problem by uninstalling xfonts-75dpi and xfonts-100dpi.
So another solution might be for nedit to recommend those fonts, as is done in grace (which is the package I happened to have installed on Vivid): 100dpi- transcoded | xfonts- 75dpi-transcode d
Recommends: xfonts-100dpi | xfonts-75dpi | xfonts-