Concur -- but, again, the first question I'd ask is whether Glen is trying to solve the right problem: It's really not at all clear from the cited symptoms that his box has been compromised. Changing the root password (accidentally or on purpose) and then forgetting having done so for quite some time would bring about the exact same situation.
That aside, the question of how you tell whether or not your system has been compromised is an interesting one: It turns out that there's no general solution, and it's always a possibility that you're operating a compromised box but just can't detect any signs.
Generally speaking, the bad guys break in because they want to do something, and so you find them by noticing something going on that shouldn't be, e.g., a sudden shortage of disk space or bandwidth that you can't account for even after careful inspection -- or weird network services that seem to be in operation when you probe the system using nmap from elsewhere on the network. But lack of such evidence just inherently isn't (and cannot be) definitive.
You should already have the ability to recover completely from such compromise. Period. If you have to live in fear of "hackers" [sic] because of lack of current, reliable backups and a realistic plan to restore from them, then the latter (lack) should be your top priority as a problem to fix, not "hackers'. After all, hardware failure -- always a strong possibility -- would face you with pretty much the same problem.
If you ever do become reasonably convinced that you've suffered root compromise, the only safe thing to do is cut power on the system immediately, then reboot the system from write-protected maintenance media long enough to confirm the symptoms and secure safety copies of any files you care about, then rebuild the system solely from trusted installation media, carefully not reusing any of the system's binaries, libraries, scripts, configuration files, or dotfiles. System configuration should be reconstructed by examining copies of the compromised system's configuration files, but not directly reusing any of them (because they cannot be trusted). When the system has been reconstructed, but before it's connected to public networks, you should apply all needed patches and updates so you can be confident in its security profile, and should issue new passwords to all logins and not let users back in until you've talked to them individually (about what they should and should not do, to keep the bad guys from getting back in). Ideally, you should have a high-probability guess about the exact method of compromise, and have acted to insure that the hole has been closed, before re-connecting the system to the outside world.
Recovery from root compromise must be done carefully and systematically, or you'll end up doing it multiple times until you get it right.
Rick Moen
rick@linuxmafia.com