Searching for "Cannot instantiate non-existent class" seems to be a fairly straight forward php problem, line 67 in Workbook.php is the important one where the new exel workbook is created
$this->tmp_format = new Format();
but before one makes an instance of the class format (an excel workbook), one must first ensure that the class itself exists using a "class declaration". I can remember this from my pascal programing dayes. You have to declare variables (or at least classes in php) before you use (an instance of) them. I do not know where the class declaration takes place, but it should take place somewhere.
One of the recommendations (on a CMS help forum) was that the you may be missing a file or your installation corrupted. If the file where the class was declared did not get uploaded you may not be missing it till now.
This declaration should be taking places in one of the files that is "required" by Workbook.php, which are (on lines 35-37:
require_once('Format.php');
require_once('OLEwriter.php');
require_once('BIFFwriter.php');
And judging from the name, and looking inside the file, this declaration seems to be taking place inside Format.php.
I tried renaming Format.php in my installation of Moodle and, yes, it does prevent my downloading excel files but alas there is no error message. I just get taken to a blank page. Hmm...it seems unlikely but is there any chance that your copy of Format.php is corrupted, rather than absent?
Format.php should be 637 lines.
I have had my upload process prevent my uploading the whole of Moodle but never in the middle of a file.
Tim
PS I know how it feels to have one's job depending upon Moodle. Since it works for me I should be donating more. Er, half my income? My wife would not approve.