When a server has been comprised, you *must* reformat the drive and reload the OS. There is no other way to be 100% certain that you've closed all of the backdoors the attacker may have setup.
Once you have the OS reinstalled, here are a couple of security tips to prevent this from happening in the future:
* Run security updates on a daily basis. With Debian-derived systems, this is as simple as 'aptitude update && aptitude upgrade'. Don't forget any custom-installed scripts when you're doing this! For instance, if you run something like ComusThumbs or ArrowTrader, be sure to regularly check their home pages for security announcements.
* Never use any unencrypted services for authentication. You mentioned FTP; anyone can sniff the network traffic and grab your FTP password. Use scp or SFTP instead. The same goes for e-mail: use TLS or SSL SMTP connections for sending mail, and SSL POP or IMAP for receiving it. If you have any web-based control panels, make sure they run over HTTPS, not HTTP. And of course, *never* use telnet to remote-connect.
Personally, on each of my dedicated boxes, the first thing I do is uninstall the unencrypted versions of every server except HTTP and SMTP; it makes it much easier to be certain that all users are using secure logins when things like FTP and POP3 aren't even available
Then I setup certificates to enable TLS over SMTP for sending mail (you need to have an unencrypted SMTP server listening for other servers sending mail to you) and an HTTPS server for all of my web control panels, like phpMyAdmin.
Anyway, good luck get your server back online!