O sshd já está em execução, conforme evidenciado pelo seu netstat. Ele também está ligado a todos os IPs (0.0.0.0 no netstat), portanto não deve haver nenhum problema.
Você tem um firewall no seu roteador? Você pode ter o encaminhamento de porta ativado, mas um firewall ainda pode estar perdendo o 22. Também é possível que seu ISP esteja bloqueando 22 antes mesmo de chegar até você. Eu também faria um iptables -F (soltar todas as regras do iptables) para ter certeza; eles retornarão em uma reinicialização (ou você poderá restaurá-los usando o iptables-restore).
Você pode confirmar que o sshd não está recusando as conexões, verificando /var/log/auth.log
para as conexões recusadas.
Se você confirmou que não tem conexões recusadas em seus logs e nenhum firewall em seu roteador, sugerimos alterar o SSH para usar uma porta diferente de 22 (uma porta alta aleatória > 1024). Você pode fazer isso editando /etc/ssh/ssh_config
e alterando "Port 22" para algo maior.
EDIT: Atualização dos comentários para salvar uma leitura; Você também deve tentar verificar a partir de um IP fora de sua rede em circunstâncias como esta. Neste caso, o ISP estava bloqueando a porta 22, e a conexão a uma porta alta internamente (especificando o IP externo) não estava funcionando, provavelmente devido à falta de NAT suspenso.