dans ce cas les procédures données sur la recherche google citée + haut devrait faire l'affaire...
Et c'est probablement avec l'user "ubuntu" que vous devez vous connecter, pas en root... M'enfin ça va dépendre de la configuration de votre VPS...
Possible que l'accès en root soit interdit par la config, d'où le soucis de reset du mot de passe qui ne semble pas fonctionner...
Vous avez essayé de vous connecter via kvm avec le mot de passe que vous avez changé ?