The version of tetex-dvips-1.0.6-11j4 included in RH6.2J does not update the fonts.map by running updmap as part of the postinstallation script, but seems to include the file statically. This works for English text and the fonts in tetex-fonts, but it doesn't include fonts include in jvf-standard-1.0, required to correctly run dvips with Japanese output from ASCII pLaTeX. My suggested solution would be to add lines to mkfontdir in either or both tetex-dvips or jvf-standard. Please see fj.comp.texhax: m34s3x4ioj.fsf
This should be fixed in 1.0.7-17.