A configuração padrão no Debian (e, portanto, no Ubuntu) para o OpenSSH Server é negar o login baseado em senha para o root e permitir somente o login baseado em chave. Altere esta linha em /etc/ssh/sshd_config :
PermitRootLogin without-password
para
PermitRootLogin yes
E reinicie o servidor SSH:
sudo service ssh restart