Você tem o ssh como root desativado? Verifique sua configuração do sshd (possivelmente /etc/ssh/sshd_config ) e procure a linha PermitRootLogin no . Altere o no para yes e reinicie o sshd (provavelmente service ssh restart ou service sshd restart ).
Algumas distribuições (por exemplo, Ubuntu) assumem o padrão de without-password para PermitRootLogin , de forma que o login de raiz é permitido via autenticação de chave pública, mas não com senha.