В зависимости от того, какой у тебя дистр курить до просветления доки по System V style init или BSD style init.

С какими симптомами не запускается. Что выводит при попытке запуска ручками?

Разкоментируй строку в inetd.conf напротив telnet сервиса и запусти inetd.

Если xinetd, то в файле /etc/xinetd.d/telnet нужно поставить disable = no

А стоИт ли?

telnet на запуск прописан в /etc/inetd.conf. Другое "радует": rpm -qi telnet-server-0.14-2mdk.i586.rpm выдает: пакет telnet-server-0.14-2mdk.i586.rpm не установлен.

rpm -i telnet-server-0.14-2mdk.i586.rpm выдает: пакет telnet-server-0.14-2mdk.i586.rpm уже установлен.

Сносить и установить заново?

Нет, не сносить, просто название пакета и название файла - это разные вещи:
0) rpm -qi telnet-server-0.14-2mdk.i586.rpm - проверяет есть ли пакет с таким названием в базе RPM или нет, естественно, что такого не будет.
Попробуй "rpm -qi telnet-server-0.14-2mdk" или лучше "rpm -qa|grep telnet";
1) rpm -i telnet-server-0.14-2mdk.i586.rpm - берет название пакета из этого файла, смотрит в базу и видит, что пакет с таким названием уже есть - поэтому и говорит, что "уже установлен"