I have tetex set up to use a local texmf tree /usr/share/texmf.local, in which I have a font (in pk form) not a part of tetex. When I give a "dvips" command directly, the font is found and used correctly. I also have /etc/printcap configured by printtool to print to a remote postscript printer, so the input filter calls dvips for dvi files. However, when I give an "lpr filename.dvi" command, the font in my local texmf tree isn't found, and cmr10 is substituted instead.
Resolved! I updated tetex to the latest version of the distribution and the problem disappeared. (Of course, I still have no idea why the problem was there in the first place.)
I'm closing this. Reopen it if your problem returns.