É assim mesmo. O ubuntu não usa senha de root; esse usuário normalmente fica desativado. Ao mesmo tempo, o primeiro usuário cadastrado [durante a instalação] é o administrador da máquina.
Então beleza, ele tem senha cadastrada; e tenho certeza de que vc está digitando a senha correta.
Vamos então ao servidor, via console, veja no log do sistema (/var/log/syslog) se há mensagem relativa a erro no sshd.
Vc pode ver também nos arquivos /var/log/messages e /var/log/auth.