I've had similar problems with ParseExcel. In such cases, I was able to use OLE to get the job done. Even using newer versions of Excel through OLE to process xls files created by old versions didn't give me any trouble.

However, I have to guess you are not a Win32 Monk. Unless another monk has a good solution, windows perl would be an easy fix. Best of luck.