I've been hacked; what to do next?

I went one one of my Mambo/php sites, instead of the usual stuff I found "HaCKeD By BeLa & BodyguarD (Turkish Hackers)". This is a PHP site and and I found a new index.html dated Jan 31.

It looks like they are very busy

http://www.google.com/search?q=bela+bodyguard

http://www.google.com/search?q=mambo+bela+bodyguard

This could be just a Mambo PHP hack (not so bad), or a full rookit (very bad). Suspecting a root kit, I installed chkrootkit & it shows:

Checking `lkm'… You have 57 process hidden for ps command

chkproc: Warning: Possible LKM Trojan installed

This does not sound good. I dont know if this is a false positive because of UML or a real rootkit. I have standard Redhat 9 running for 3 years, all passwords are mine an alpha-numeric, firehol is used as the firewall. I'm currently backing up everything using rsync.

So where do I go from here? I have no idea how this was done, they didn't seem to vandalise anything just show their presence. I suppose I will have to start again with a new distro and rebuild from scratch.