Verifique o arquivo / etc / ttys que contém uma lista de terminais. Somente aqueles marcados como "seguros" permitirão que o root faça o login. Por padrão, este é o console e todos os terminais virtuais. Os pseudo-terminais não permitem login raiz.
Além disso, hoje em dia, onde a segurança é uma grande preocupação, posso perguntar por que você ainda está usando um protocolo não seguro como o telnet e não o ssh?
(edit) graças ao James, eu percebi que eu encobri o FreeBSD e sugeri a solução que sempre usei e dei como certo no Linux. A menos que você tenha o complemento de segurança do PAM ativado, você não terá esse arquivo. Em vez disso, use o arquivo mencionado por James na resposta acima.