Telnet connection to Debian machine refused

The in.telnetd binary in package telnetd is running by default as an unprivileged process with user telnetd, probably for security reasons and privileges separation:

# grep telnet /etc/inetd.conf 
telnet      stream  tcp nowait  telnetd /usr/sbin/tcpd  /usr/sbin/in.telnetd

It then uses an helper process for handling the actual login. This helper process is setuid root. On a Debian 8 system that would give (except the date and size of the file, the same as on Debian 10):

# dpkg -S /usr/lib/telnetlogin
telnetd: /usr/lib/telnetlogin
# ls -l /usr/lib/telnetlogin
-rwsr-xr-x. 1 root telnetd 8112 Jul 22  2008 /usr/lib/telnetlogin

If you remove the setuid bit to this helper, you get exactly OP's error message.

This setuid bit is normally set during the package's post-installation in /var/lib/dpkg/info/telnetd.postinst:

if [ -z "$(dpkg-statoverride --list /usr/lib/telnetlogin)" ]; then
  chown root:telnetd /usr/lib/telnetlogin
  chmod 4754 /usr/lib/telnetlogin
fi

For example the set-uid bit could have been manually removed, overriden in dpkg-statoverride's database or the package not been completely installed. Or OP's in.telnetd is running in a restricted environment. Some examples could be a filesystem mounted with nosuid, perhaps including containers, or unadequate settings with AppArmor or SELinux.

Of course using telnetd itself should never be done. There used to be an SSL version available for telnet client and server, but considering it's not available in Debian stable (but only sid) it might have issues on its own.