telnet - no route to host

При попытке зателнетить 25 порт на определенном хосте выдает:
Trying 123.456.789.012...
telnet: connect to address 123.456.789.012: No route to host

При этом нужный сервис включен на сервере,
tcp 0 0 0.0.0.0:25 0.0.0.0:* LISTEN

и сервер пингуется.

В этом случае вероятнее всего телнет запилен фаерволом самого сервера или роутера.
Если на самом сервере то можно проверить это отключив файервол на нем:
/etc/init.d/iptables stop
или
service iptanles stop
Но если это сделано не вами и сделано осознано, значит это имеет смысл.