SSHD rootkit, cPanel affected

As a follow-up to the previous post, it has now been confirmed that there is an SSHD rootkit in the wild that spreads itself if you ssh from an infected server to another. The details are explained in this article as a summary of the webhostingtalk thread:
http://isc.sans.edu/diary/SSHD+rootkit+in+the+wild/15229
Unfortunately, cPanel is a victim of this malware and their workstation(s) have been infected leading to possible infection of client servers:

Salutations,
You are receiving this email because you have opened a ticket with our support staff in the last 6 months. cPanel, Inc. has discovered that one of the servers we utilize in the technical support department has been compromised. While we do not know if your machine is affected, you should change your root level password if you are not already using ssh keys. If you are using an unprivileged account with “sudo” or “su” for root logins, we recommend you change the account password. Even if you are using ssh keys we still recommend rotating keys on a regular basis.
As we do not know the exact nature of this compromise we are asking for customers to take immediate action on their own servers. cPanel's security team is continuing to investigate the nature of this security issue.
–cPanel Security Team

We would recommend (as we do on our helpdesk) that you change your root passwords immediately after any third-party has accessed your server. Additionally, to those affected, please remember that you cannot “clean” this infection, you must reinstall your OS and restore user accounts from backups.