texlive-lang-czechslovak требует texmf(latex/lmodern) Надо либо собрать lmodern в составе texlive (выкинут в Debian), либо отдельным пакетом.
Включил в texlive.