Same problem on upgrade from 12.04 LTS to 14.04 LTS.
As inspired by the comments #9 and #10 I worked around with
sudo apt-get remove --purge tex-common texlive-* sudo rm /etc/texmf/ sudo apt-get install tex-common sudo apt-get install texlive-base sudo apt-get install texlive-latex-recommended
Run without any errors.
Same problem on upgrade from 12.04 LTS to 14.04 LTS.
As inspired by the comments #9 and #10 I worked around with
sudo apt-get remove --purge tex-common texlive-* latex-recommend ed
sudo rm /etc/texmf/
sudo apt-get install tex-common
sudo apt-get install texlive-base
sudo apt-get install texlive-
Run without any errors.