Had the same on 2 of my dedicated servers within the past 3 month. One server was somewhat easy to restore, however it was hit twice. Once right after I fixed it the first time. The sites were in svn, so just a couple of clicks here and there. I noticed some Russian admin php script was added to phpmyadmin directory. Was pretty nice actually, don't remember the name off the top of my head. I looked all over, couldn't find how they got in, but found a few 777 folders that I changed back and added server authorization to phpmyadmin folder. Haven't had a problem since then.
The other server was centos. Was a pain to go through all the files and fix them. Pretty easy to find all the files though since the change time was within an hour on a certain date. Disabled ftp on that server.