Como o bodhi.zazen menciona, o login root do ssh pode estar desabilitado.
Honestamente, isso não é uma coisa ruim. Você pode querer considerar se acostumar a ter que "su -" para root se você tiver que (ou sudo -i se você usá-lo).
Tente o seguinte para verificar,
grep PermitRootLogin /etc/ssh/sshd_config
Se você vir o seguinte, o login do usuário root será desativado.
PermitRootLogin no
Ou se a saída for a seguinte, o login root não pode ser feito com senhas:
PermitRootLogin without-password
Para alterar essa configuração, use seu editor de texto favorito (vi / nano) e altere não para "yes"
Novamente, considere se acostumar a trabalhar com "su - / sudo" quando necessário antes de alterar isso.
EDIT / Sidenote: Além disso, isso só funcionará se você realmente definir uma senha para o usuário root.