How did the attackers know what they were looking for. I'm going to assume that it's a small minority of linode users who have bitcoins on their machines. How were just these users targeted so accurately? What tied together knowledge they used bitcoins to those VMs and their linode accounts? Also, was the nature of the attack just that the were able to login to your linode admin panel and from their root the machines…
The way I understand it the attackers were able to get access to the admin panel and invoked some kind of 'change root password' emergency stuff. The machines were rebooted it seems, which makes sense: The interface of Linode has probably/hopefully no access to the root password. Maybe this 'Reset my root' feature (now I'm guessing) reboots the machine in single user mode or passes init=/bin/sh to the kernel to reset the password once and reboots again afterwards.
Only THEN the attacker had access. But yes, he had root. The good (if you want to call it that) part of it is that this procedure rings every alarm possible. The real owner doesn't have the password anymore, as he'll soon figure out. It's everything but sneaky.
I DO wonder why root is allowed to log in at all, though..