Linode does offer basic two-factor authentication, which was one of the things I mentioned. You have the ability to set up IP address whitelists. If you try to log in from an address not on the whitelist, you get an email to confirm you are who you say you are. If I know the attack correctly, the hacker reset (or otherwise gained) the password via the support console and used that to log in. With two-factor, he could get the right password but would still need access to the email account as well. Unless you've majorly fucked up, there is no way anyone besides you is getting root.

You sign no SLA with Linode. They make no guarantees. That leaves it up to you to make sure you're secure, and fortunately they give you the tools needed to make this a reality.