With the latest update of texlive-core, some new hyphenation patterns cause TeX capacity to be exceeded when some formats are created. In the file /usr/share/texmf/web2c/texmf.cnf, change the line trie_size = 600000 to trie_size = 700000 Then run sudo fmtutil-sys --missing and everything will be fine.
Note on fresh TeXLive installs
2008-12-03 - François Charette