snip...
If the regular tools do not find it, file bugs against them (or even file them upstream to reduce turn around time). Additionally, you could upload all suspect files to virustotal - where they are handed off to all the major AV vendors (mostly useful for mail gateways and that other wormy OS).
supaplex@tv:~$ apt-cache search rootkit
chkrootkit - rootkit detector
rkhunter - rootkit, backdoor, sniffer and exploit scanner
unhide - Forensic tool to find hidden processes and ports
unhide.rb - Forensic tool to find processes hidden by rootkits