Ok. Your goal will be to reformat your drive and then reinstall Linux from scratch. Sorry, ain't no other way.Eventually, the machine did have to be completely rebuilt. Since then I've had a heightened interest in how these things happen.
Last weekend, slashdot had an article linking to a story on brute force ssh attacks. While we guessed that this was what had happened to us, one user's comment showing an excerpt of attempted logins convinced me that our guess was correct.
Driving home the issue even further, via TinyApps.Org's blog, are these movies (flash) demonstrating how quickly and easily these attacks work. I've only watched a couple of these and for linux/unix geeks, it's spookier than anything Hollywood could produce. You see one step then another and then you realize what's going to happen and there's nothing you can do to stop it.
p.s. These movies demonstrate the Whoppix/Whax tool. If an admin of this site has found this post, please take a moment to add a brief "About this tool" to your site. It wasn't until I googled my way to distrowatch.com that I learned that
Whoppix is a stand-alone penetration-testing live CD based on KNOPPIX. With the latest tools and exploits, it is a must for every penetration tester and security auditor. Whoppix includes several exploit archives, such as Securityfocus, Packetstorm, SecurityForest and Milw0rm, as well as a wide variety of updated security tools.