An installation from scratch is necessary; the damage is done. There are a bunch of root exploits, some to do with certain kernel versions, others to do with certain versions of OpenSSH (although, as Jon claimed, they tend to be theoretical rather than in-the-wild).
I'd run Tripwire and then run a vulnerability assessment scan with Nessus before putting the machine live on the 'net. I don't consider Webmin to be a security-conscious, gotta-have-it service on a production web server.
Also, considering that this appears to be your second break-in, I suggest that you find someone else to lock down your box. But that's just me.
