Do you have ssh as root disabled check? Check your sshd configuration (possilbypossibly /etc/ssh/sshd_config) and look for the line PermitRootLogin no. Change the no to yes and restart sshd (most likely either service ssh restart or service sshd restart).
Some distributions (e.g., Ubuntu) default to without-password for PermitRootLogin such that root login is allowed via public key authentication, but not with a password.