Edit: Eu pulei direto para o final da pergunta e não tinha notado que você estava tentando fazer login com uma conta de usuário normal para começar. O seguinte explica porque o root login remoto não funciona por padrão no Ubuntu. De qualquer forma, parece ter ajudado.
Para o usuário normal, basta olhar em /var/log/auth.log . Ele lhe dirá exatamente qual é o problema e isso deve lhe dar uma ideia bastante decente do que você precisa fazer.
Mas, para problemas de raiz, há um pequeno bloqueio em /etc/ssh/sshd_config .
# Authentication:
LoginGraceTime 120
PermitRootLogin without-password
StrictModes yes
Esse é o padrão e isso significa que só permitirá a autenticação baseada em chave SSH para o root.
Não permitirá que você faça login com uma senha.
Obviamente, você pode alterar a configuração para yes , mas você está começando a desvendar a segurança do Ubuntu. Ter um login de raiz de trabalho (especialmente com uma senha super-crackable) é geralmente uma idéia bastante terrível (e desnecessária). Seria mais fácil usar apenas uma chave SSH.