Well, Looks like I might have to do a server restore. I just need to know the following:

a.) Will I be able to backup anything (i.e. clients, http/cgi files, mysql databases)

b.) How long does it usually take and how much downtime?

If you can get shell access to your box, then you may be able to do backups. If not, then try ftp. After those are out, there only thing you can try to get RS today is to mount your current drive as slave in the new box and then recover the data.

Expect 1-2 hours for priority service and up to 24 hours for normal service. Then you have to get you box running again -- this can take anywhere from a few hours to days depending on the number of sites, databases, etc.

Also, if you were running your own DNS, you domain names may drop out of propagation unless you have a true backup DNS server.

Maybe I'm being stupid but what exactly does your server do?
Is is just plesk that is corrupted or the rest of your server?
If you have telnet or ssh access I would try following the instructions for upgrading from plesk 2.0 to 2.5 using plesk backup utilitys. Search this forum un the "how to" section. Make any backups possible before doing this and make sure that you use the backup utilitys that are compatible with the plesk that you are installing.
If it works it could save you alot of time and effort and money,

Richard