Getting access to the Linode admin UI doesn't give access to the server itself. You can view the console, but you just get the login prompt. You still need the server's password to log in.
To reset the password the server has to be shut down so that /etc/shadow can be modified. At that point they could just go in and grab the data, but they most likely used Linode's password changer to minimize the downtime to a few seconds to help prevent getting caught.
A reboot wouldn't be required if they got access to the Linode hosts, but it doesn't sound like that was the case here. I'm guessing the exploit is in their web-based server management.
This is by far one of the scariest things about the process. Considering Slush and the Faucet were compromised at roughly the same time, it points to the flaw being in Linode's administrative control panel. A -very- scary situation, considering Linode is one of the largest VPS providers around.
I'm late to the party. None of my bitcoind Linodes have been compromised...yet. Come and get 'em...all my coins are hot now.