We only realized the machine was compromised because the interloper decided to pick two user accounts at random and delete them (another brilliant move).
Upon investigation I found that a keylogger had been installed in order to discover the root password. I inspected the output of the keylogger to trace the attacker's steps. Similar to the SSH scan in the article, the attacker had logged into his own FTP server to download various scripts and crackers. Well, the keylogger had logged his FTP password as well (whoops). Naturally I logged in and deleted absolutely everything in sight. :-P