No I didn't change the password. Instead I rebuilt the machine from the base OS image. Would you expect that a new system with the disk wiped would retain the old root password? I certainly wouldn't. Where were they keeping it?
That is a bit ridiculous that they retained your password. Still though, logging in after rebuilding and configuring your system would have been a sane move.
Probably not strictly related (it would seem the attack in question was via a compromised (on whoever's end) ssh password), but in any case good practice: always regenerate ssh keys after installation from a base image. Some OS images may contain pregenerated keypairs (private key is usually at ~/.ssh/id_rsa ), which should always be regenerated. (This bit is most probably not actually related to the issue at hand, but IAC should not be forgotten.)