Well, it seems it has to be a connectivity issue. I disabled all the firewalls (the machine attempting to connect has two - Windows and Kaspersky), and still cannot get telnet to work. However it works just fine on port 80. I suspect it is some sort of setting in the DLink router, but what it is remains a mystery. I'll post the cause if we ever find it.