First, we have to find out what is the problem. Because we can access the target machine we can check the logs of authentication after a failed login attempt:
root@metasploitable:~# cat /var/log/auth.log
...
Jun 27 01:08:25 metasploitable rlogind[8491]: pam_securetty(rlogin:auth): access denied: tty 'pts/0' is not secure
...
I don't know what is pam securetty, so let's check it:
http://linux.die.net/man/8/pam_securetty
"pam_securetty is a PAM module that allows root logins only if the user is logging in on a "secure" tty, as defined by the listing in /etc/securetty. pam_securetty also checks to make sure that /etc/securetty is a plain file and not world writable."
Okay, next step: Let's check this file:
root@metasploitable:~# cat /etc/securetty
# /etc/securetty: list of terminals on which root is allowed to login.
# See securetty(5) and login(1).
console
...
# General
pts/1
pts/2
...
Okay, the problem is that, there is no pts/0. But we are lucky because pts/1 is allowed to login.
So the trick is this:
1) Open 2 kali terminal
2) Try to login from them at the same time:
# rlogin -l root <IP>
3) profit