TeX Live 2004 changed the location of and searching for font map (.map) and encoding (.enc) files. The TeX Live documentation briefly describes these changes; this web page goes into more detail. (It is based on the teTeX documentation.)
Following a change introduced with version 1.1 of the TeX Directory Structure document, font map files (.map) are now only searched in subdirectories of fonts/map in a given texmf tree. The subdirectories fontname/, dvips/, and pdftex/ are no longer searched for these files, as they were in previous releases. The texmf trees from TeX Live follow this convention already, but you will probably need to rearrange some files if you maintain fonts in a local texmf tree.
Within the fonts/map tree, files are organized by syntax and package. Known map file syntaxes are dvips (this is the most common one), pdftex (a superset of the dvips syntax, e.g., the psname field is optional), dvipdfm, and vtex.
Thus, just because some file is stored within the fonts/map/dvips subtree, this does not mean that dvips is the only program that accesses these files. Other programs which support the same syntax can use these files as well. It's just that "dvips" is the name for this syntax (the dvips program was its originator).
The next directory level specifies the package to which the map file belongs.
Example: the file charter.map of the psnfss package follows the dvips syntax, so it is stored in fonts/map/dvips/psnfss/charter.map.
If you find that an application cannot find a map file which is stored in a wrong location, you have to move that file to the right location. Try to find out the syntax and the package that the file belongs to. If unsure, you can always choose unknown, since the only restriction for the directory tree below fonts/map is that all file names are unique; the precise syntax/package subdirectory does not affect searching.
After making any changes to file locations, do not forget to update the filename database (ls-R) by running the command mktexlsr.
Map files were previously searched for along the $TEXCONFIG variable ("dvips config" format for kpathsea clients). This has been changed to the $TEXFONTMAPS variable ("map" format).
The new location of the font map files is included in the new default setting of $TEXFONTMAPS, but not in the default setting of $TEXCONFIG. The result is that an old application that searches font map files along the "dvips config" format will not work.
For C clients of kpathsea, this means that map files should be accessed using kpse_fontmap_format instead of kpse_dvips_config_format. For scripts that use kpsewhich, one muse use the --format=map option to search for font map files.
Like font map files (see above), font encoding files have been given a new location and a new search path. The new location is fonts/enc/syntax/package, and the new search path is $ENCFONTS (kpse_enc_format, --format=enc).
Again, if some application fails to find a font encoding file, move it to the right location in the texmf tree and update the filename database.
If you are unable or unwilling to move files, you can change the search paths to find .map/.enc files anywhere in the tree with these simple settings:
TEXFONTMAPS = .;$TEXMF// ENCFONTS = .;$TEXMF//
This can be done in texmf.cnf, as environment variables, or however your local setup permits.
Of course, we encourage following the TDS if at all feasible.
You may reasonably ask why we made this incompatible change. We discussed it at length. This message (and thread) has some of the discussion.
The principal reason is that making the paths compatible also has associated problems. We have to search the new directories before the old directories, naturally. But then, if a modified psfonts.map (say) has been installed in a local texmf tree, in the old directory, it would not be found before the system .map file. This violates the principle that local modification should override the system defaults.
Since we could find no way to satisfy all requirements, we decided a clean break was simplest to understand: new directories, new search paths. It only affects installations with local map/enc installed.
We regret the inevitable confusion and extra work for those affected.