Hay tantas variables que se pueden verificar que el post se nos haría eterno. Te pongo algunos apuntes:
- Verifica el /etc/hosts.allow /etc/hosts.deny
- Verifica que los DNS funcionen correctamente.
- Reinstala el sshd por si estuviera troyanizado. (Dices que no te va el apt-get. Mala señal
)
- Pásale algún verificador de rootkits:
http://www.chkrootkit.org/download.htm o
http://rkhunter.sourceforge.net/
Si aún así nada, a lo mejor tardas menos en sacar una copia de seguridad y reinstalar desde 0 el sistema.