Только что проверил у себя:
[dkoryavov@koryavov-note ~]$ sudo apt-get install evince-dvi
[sudo] password for dkoryavov:
Чтение списков пакетов... Завершено
Построение дерева зависимостей... Завершено
Следующие дополнительные пакеты будут установлены:
tetex-core tex-common
Следующие НОВЫЕ пакеты будут установлены:
evince-dvi tetex-core tex-common
0 будет обновлено, 3 новых установлено, 0 пакетов будет удалено и 37 не будет обновлено.
Необходимо получить 19,9MB архивов.
После распаковки потребуется дополнительно 69,8MB дискового пространства.
Продолжить? [Y/n] y
Получено: 1 ftp://ftp.altlinux.org noarch/classic tex-common 0.2-alt4 [4867B]
Получено: 2 ftp://ftp.altlinux.org i586/classic tetex-core 2.0-alt10 [19,9MB]
Получено: 3 ftp://ftp.altlinux.org i586/classic evince-dvi 2.28.1-alt1 [56,1kB]
Получено 19,9MB за 1m17s (258kB/s).
Совершаем изменения...
Preparing... ################################################################################################### [100%]
1: tex-common ################################################################################################### [ 33%]
2: tetex-core ################################################################################################### [ 66%]
3: evince-dvi ################################################################################################### [100%]
Running /usr/lib/rpm/posttrans-filetriggers
Завершено.
[dkoryavov@koryavov-note ~]$
Как видите, никаких проблем. Видимо, Вы неверно настроили репозитории, либо проблема в конфликте texlive с tetex.