Нужны дополнительные сведения (с полными именами и версиями пакетов): 
- что именно устанавливалось, когда возникла эта ошибка,
- что уже было установлено из относящегося к ТеХу перед этим в системе
- что содержится в файлах ls-R, на которые ругается скрипт?

(В ответ на комментарий №1)
> Нужны дополнительные сведения (с полными именами и версиями пакетов): 
> - что именно устанавливалось, когда возникла эта ошибка,

Я ставил xneur, libxneur, gxneur: https://bugzilla.altlinux.org/show_bug.cgi?id=22769

Но я совсем не уверен, что ошибка не появилась ранее.

> - что уже было установлено из относящегося к ТеХу перед этим в системе

$ cat /etc/apt/sources.list
rpm ftp://gate.tts.loc/pub/ALTLinux/distributions/4.1/branch/ i586 classic
rpm ftp://gate.tts.loc/pub/ALTLinux/distributions/4.1/branch/ noarch classic

$ rpm -qa | grep ^te[xt] | sort
tex-common-0.2-alt4
texinfo-4.13-alt6
texlive-base-2008.0-alt0.13
texlive-base-bin-2008.0-alt0.12
texlive-common-0.1-alt3
texlive-doc-base-2008.0-alt0.10
texlive-font-utils-2008.0-alt0.12
texlive-latex-base-2008.0-alt0.13
texlive-omega-2008.0-alt0.12

> - что содержится в файлах ls-R, на которые ругается скрипт?
# file /usr/share/texmf/doc/ls-R
/usr/share/texmf/doc/ls-R: data
# file /usr/share/texmf-texlive/ls-R
/usr/share/texmf-texlive/ls-R: data
# file /usr/share/texmf/ls-R
/usr/share/texmf/ls-R: DOS executable (device driver) for DOS
# file /etc/texmf/ls-R
/etc/texmf/ls-R: data
# file /var/cache/texmf/ls-R
/var/cache/texmf/ls-R: ASCII text
# cat /var/cache/texmf/ls-R
.6.25-std-def-alt8.M41.1/kernel/crypto/seqiv.ko
/lib/modules/2.6.25-std-def-alt8.M41.1/kernel/crypto/serpent.ko
/lib/modules/2.6.25-std-def-alt8.M41.1/kernel/crypto/sha1_generic.ko
/lib/modules/2.6.25-std-def-al

> > - что содержится в файлах ls-R, на которые ругается скрипт?

Такое впечатление, что у Вас в этих файлах содержится мусор. 
Вы давно проверяли файловую систему?

> # file /usr/share/texmf/doc/ls-R
> /usr/share/texmf/doc/ls-R: data
> # file /usr/share/texmf-texlive/ls-R
> /usr/share/texmf-texlive/ls-R: data
> # file /usr/share/texmf/ls-R
> /usr/share/texmf/ls-R: DOS executable (device driver) for DOS
> # file /etc/texmf/ls-R
> /etc/texmf/ls-R: data
> # file /var/cache/texmf/ls-R
> /var/cache/texmf/ls-R: ASCII text
> # cat /var/cache/texmf/ls-R
> .6.25-std-def-alt8.M41.1/kernel/crypto/seqiv.ko
> /lib/modules/2.6.25-std-def-alt8.M41.1/kernel/crypto/serpent.ko
> /lib/modules/2.6.25-std-def-alt8.M41.1/kernel/crypto/sha1_generic.ko
> /lib/modules/2.6.25-std-def-al

У меня тоже такое впечатление. Удалять-то их можно? Нужно ли потом пустые создавать? Или где-то оригиналы лежат?

Файловую систему руками не проверял никогда на этой машине. А когда оно автоматом запускалось, тоже не смотрел.

Завтра с утра запущу проверку...

(В ответ на комментарий №4)
> У меня тоже такое впечатление. Удалять-то их можно? Нужно ли потом пустые
> создавать? Или где-то оригиналы лежат?
Это базы данных установленных файлов в TEXMF-деревьях, для быстрого поиска
с помощью библиотеки kpathsea.
Если файлы действительно битые, достаточно их удалить и запустить от рута
mktexlsr

Помогло, спасибо!
Извините за беспокойство.