Simplesmente adicionar uma senha para root não é suficiente para o Ubuntu 14.04 Server.
Você também precisa editar /etc/ssh/sshd_config
e comentar a seguinte linha:
PermitRootLogin without-password
Logo abaixo, adicione a seguinte linha:
PermitRootLogin yes
Em seguida, reinicie o SSH:
service ssh reload
Para o Ubuntu 16.04.1 LTS (GNU / Linux 4.4.0-59-genérico x86_64) PermitRootLogin without-password
foi substituído por PermitRootLogin prohibit-password
.