I'd start with checking that root is allowed to login at all. Second thought: given that you purchased your server from abroad it might be installed with a locale that is different from what you expect. Reset the password again and use only chars and numbers to prevent you being tricked by a wrong keyboard layout.