If somebody gets root control of your system the only 100% safe solution is to reinstall from known good CD's*. That doesn't matter if your talking about Windows or Linux or an other OS.
But there is a key difference. Getting rooted under Linux is a rare event, getting rooted under Windows is a nearly unavoidable every day event.
Jay
* Some root kits have been working on the idea of installing to BIOS which would make even that insufficient.