Eu sei que você provavelmente fez isso, mas na máquina que você está tentando se conectar, o netstat -a lhe dá algo assim:
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address Foreign Address State
tcp 0 0 *:ssh *:* LISTEN
tcp 0 0 192.168.1.30:ssh 192.168.1.72:46480 ESTABLISHED
tcp6 0 0 [::]:ssh [::]:* LISTEN
Pelo menos uma das linhas deve mostrar algo como *: ssh para conexões ssh a serem estabelecidas para aquela máquina.
Se não, então o sshd precisa ser iniciado ...