In a comment on a similar looking bug (https://bugzilla.redhat.com/show_bug.cgi?id=739643) Jindrich Novy says: 

"Problems may arise if you update from older versions of TeX Live 2010 where post-install scriptlets could cause havoc or e.g. updmap.cfg was already in inconsistent state.

Please remove the old installation completely and install it again without updating from the previous versions."

This is unlikely be a problem, because it's a brand new install of Fedora 19.
Unless having a ~/.texlive2007 counts. I renamed it, but that didn't help.

Created attachment 785416 [details]
list of texlive packages I had when the problem occurred

Created attachment 785417 [details]
the list of extra packages

After installing a number of extra texlive packages (see attachment!) the problem went away. I don't know if it counts as a dependency bug or not.

Actually I think the problem occurred due to the change in texmf-dist path. It seems it has been moved from the old path. Removing the packages did not work for me. I did a symlink to its old path put texmf-config/ls-R to texmf-dist and then I did a texconfig rehash. After that I did fmtutils-sys --all. 

after that everything was ok.

My clean install failed with the same error:
"fmtutil: config file `fmtutil.cnf' not found."

Installing texlive-texconfig-bin solved it, so my guess is that there is a missing dependency on textlive-texconfig for some package.

This causes FTBFS of kannel.

Comment 5 solves the problem, so I think it's a dependency problem.

F20 user here. I had texlive-texconfig-bin package installed and still had the problem. I've installed texlive-collection-latex-3:svn30308.0-5.20131226_r32488.fc20.noarch as per suggestion from http://thread.gmane.org/gmane.linux.redhat.fedora.general/435441/focus=435452 and issued "sudo texconfig rehash" per suggestion from http://tex.stackexchange.com/a/64895/64667, and my pdflatex definitely progressed further. I am not sure the additional packages helped but I'd installed following:

Installing:
 texlive-collection-latex         noarch 3:svn30308.0-5.20131226_r32488.fc20 updates
Installing for dependencies:
 libpaper                         i686   1.1.24-7.fc20                       fedora 
 texlive-ae                       noarch 3:svn15878.1.4-5.fc20               updates
 texlive-amscls                   noarch 3:svn30738.0-5.fc20                 updates
 texlive-babel-english            noarch 3:svn30264.0-5.fc20                 updates
 texlive-beton                    noarch 3:svn15878.0-5.fc20                 updates
 texlive-bibtex                   noarch 3:svn29764.0.99d-5.fc20             updates
 texlive-bibtex-bin               i686   3:svn30088.0-5.20131226_r32488.fc20 updates
 texlive-cm                       noarch 3:svn29581.0-5.fc20                 updates
 texlive-collection-basic         noarch 3:svn30372.0-5.20131226_r32488.fc20 updates
 texlive-dvipdfmx                 noarch 3:svn32380.0-5.fc20                 updates
 texlive-dvipdfmx-bin             i686   3:svn30845.0-5.20131226_r32488.fc20 updates
 texlive-dvipdfmx-def             noarch 3:svn31722.0-5.fc20                 updates
 texlive-dvips                    noarch 3:svn32380.0-5.fc20                 updates
 texlive-dvips-bin                i686   3:svn30088.0-5.20131226_r32488.fc20 updates
 texlive-enctex                   noarch 3:svn28602.0-5.fc20                 updates
 texlive-etex                     noarch 3:svn31600.2.1-5.fc20               updates
 texlive-euler                    noarch 3:svn17261.2.5-5.fc20               updates
 texlive-fancyhdr                 noarch 3:svn15878.3.1-5.fc20               updates
 texlive-fix2col                  noarch 3:svn17133.0-5.fc20                 updates
 texlive-glyphlist                noarch 3:svn28576.0-5.fc20                 updates
 texlive-gsftopk                  noarch 3:svn29764.1.19.2-5.fc20            updates
 texlive-gsftopk-bin              i686   3:svn30088.0-5.20131226_r32488.fc20 updates
 texlive-hyph-utf8                noarch 3:svn30757.0-5.fc20                 updates
 texlive-ifluatex                 noarch 3:svn26725.1.3-5.fc20               updates
 texlive-ltxmisc                  noarch 3:svn21927.0-5.fc20                 updates
 texlive-lua-alt-getopt           noarch 3:svn29349.0.7.0-5.fc20             updates
 texlive-makeindex                noarch 3:svn29764.2.12-5.fc20              updates
 texlive-makeindex-bin            i686   3:svn30088.0-5.20131226_r32488.fc20 updates
 texlive-metafont                 noarch 3:svn29764.2.718281-5.fc20          updates
 texlive-metafont-bin             i686   3:svn30088.0-5.20131226_r32488.fc20 updates
 texlive-mflogo                   noarch 3:svn17487.0-5.fc20                 updates
 texlive-mfnfss                   noarch 3:svn19410.0-5.fc20                 updates
 texlive-mfware                   noarch 3:svn29764.0-5.fc20                 updates
 texlive-mfware-bin               i686   3:svn30088.0-5.20131226_r32488.fc20 updates
 texlive-misc                     noarch 3:svn24955.0-5.fc20                 updates
 texlive-mptopdf                  noarch 3:svn29751.0-5.fc20                 updates
 texlive-mptopdf-bin              noarch 3:svn18674.0-5.20131226_r32488.fc20 updates
 texlive-natbib                   noarch 3:svn20668.8.31b-5.fc20             updates
 texlive-pdftex-def               noarch 3:svn22653.0.06d-5.fc20             updates
 texlive-plain                    noarch 3:svn26647.0-5.fc20                 updates
 texlive-pslatex                  noarch 3:svn16416.0-5.fc20                 updates
 texlive-pspicture                noarch 3:svn15878.0-5.fc20                 updates
 texlive-tex                      noarch 3:svn29764.3.1415926-5.fc20         updates
 texlive-tex-bin                  i686   3:svn30088.0-5.20131226_r32488.fc20 updates
 texlive-texconfig                noarch 3:svn29764.0-5.fc20                 updates
 texlive-texconfig-bin            noarch 3:svn29741.0-5.20131226_r32488.fc20 updates
 texlive-texlive-common-doc       noarch 3:svn30524.0-5.fc20                 updates
 texlive-texlive-en-doc           noarch 3:svn32016.0-5.fc20                 updates
 texlive-texlive-msg-translations noarch 3:svn31379.0-5.fc20                 updates
 texlive-texlive-scripts          noarch 3:svn32466.0-5.fc20                 updates
 texlive-texlive-scripts-bin      noarch 3:svn29741.0-5.20131226_r32488.fc20 updates
 texlive-xdvi                     noarch 3:svn30339.22.86-5.fc20             updates
 texlive-xdvi-bin                 i686   3:svn30088.0-5.20131226_r32488.fc20 updates

Fedora 22, fresh install, nothing TeX-related ever installed on this machine before today. I wanted to use Pandoc to convert some Markdown to a PDF: `pandoc -t latex foo.md -o foo.pdf` instructed me to install pdflatex.

Installing texlive-latex-bin-bin (via command-not-found) pulled in 108 other packages http://fpaste.org/251029/14386135/ but pdflatex still didn't work at all:

    % pdflatex foo.tex
    This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2014) (preloaded format=pdflatex)
     restricted \write18 enabled.

    kpathsea: Running mktexfmt pdflatex.fmt
    /usr/bin/mktexfmt: line 395: /usr/share/texlive/texmf-dist/texconfig/tcfmgr: No such file or directory
    fmtutil: config file `fmtutil.cnf' not found.
    I can't find the format file `pdflatex.fmt'!

Installing texlive-texconfig (and texlive-texconfig-bin) allowed it to make more progress: http://fpaste.org/251031/86136421/ and:

    % pandoc -t latex foo.md -o foo.pdf
    ! Font OT1/cmr/m/n/10=cmr10 at 10.0pt not loadable: Metric (TFM) file not found
    .
    <to be read again> 
                       relax 
    l.64 \normalsize

    pandoc: Error producing PDF from TeX source

Installing texlive-collection-fontsrecommended finally did the trick.

So it seems to me like texlive-latex-bin-bin (or one of its dependencies…) is missing at least a dependency on texlive-texconfig. I don't know whether something should have depended on some fonts… or maybe pandoc needs a supplementary package to install all the dependencies to make its PDF-via-LaTeX output work? (I guess in Debian terms the fonts might be Recommended:, but I don't think RPM has an equivalent.)

This package has changed ownership in the Fedora Package Database.  Reassigning to the new owner of this component.

texlive-2014-13.20140525_r34255.fc23 has been pushed to the Fedora 23 testing repository. If problems still persist, please make note of it in this bug report.
If you want to test the update, you can install it with
$ su -c 'dnf --enablerepo=updates-testing update texlive'
You can provide feedback for this update here: https://bodhi.fedoraproject.org/updates/FEDORA-2015-16620

texlive-2014-10.20140525_r34255.fc22 has been pushed to the Fedora 22 testing repository. If problems still persist, please make note of it in this bug report.
If you want to test the update, you can install it with
$ su -c 'dnf --enablerepo=updates-testing update texlive'
You can provide feedback for this update here: https://bodhi.fedoraproject.org/updates/FEDORA-2015-16621

texlive-2014-13.20140525_r34255.fc23 has been pushed to the Fedora 23 stable repository. If problems still persist, please make note of it in this bug report.

texlive-2014-10.20140525_r34255.fc22 has been pushed to the Fedora 22 stable repository. If problems still persist, please make note of it in this bug report.