Comment 2 for bug 36536

It _seems_ I found a solution to at least work around this: After reconfiguring _all_ installed tetex packages issuing

dpkg-reconfigure `dpkg -l|grep ^ii|grep tetex|awk '{print $2}'|xargs`

hyphenation now seems to work on both of my machines. But this doesn't explain why it is broken "by default" after a clean installation.