Explorer.exe Error on Boot

Got a W2k mahcine that boots into nothing but error pop up box after pop up box saying that explorer.exe generated errors and will be shut down. Error log being made, bla, blah, BLAH!
No icons, no start bar. Just those errors. We can boot into safe mode with DOS prompt and tried replacing explorer.exe to no avail.
Any suggestions?