OT1 and Times

Not sure if this is a teTeX problem or maybe a dvips or kpathsearch
problem, but since it broke with teTeX 3.0, I am asking here:

We cannot get standard PostScript fonts like Times to work with OT1
encoding anymore.  Here is a test document:

\documentclass{minimal}
\usepackage{times}
\begin{document}
Testing, testing.
\end{document}

I run latex on it and get a dvi file containing this font (according
to dvitype):

Font 14: ptmr7t 

if I run dvips on it, I get

kpathsea: Running mktexpk --mfmode ljfour --bdpi 600 --mag 1+0/600 --dpi 600 ptmr0
mktexpk: don't know how to create bitmap font for ptmr0.
kpathsea: Appending font creation commands to missfont.log.
/store/bin/dvips: Font ptmr0 not found,  using cmr10 instead.

and similarly if I run pdflatex on the original latex file.

I have been telling users that the problem goes away if they use T1
encoding instead, but since this usage is quite widespread, I would
like to know what is going on, and how to fix it if possible.

This definitely worked well with teTeX 2.0.2.  But I don't know WHY it
worked, since ptmr7t and ptmb7t entries were absent from the map files
even then.  And since I don't understand why it worked previously, I
don't really know where to start debugging the problem.  Can someone
point me in the right direction?

- Harald