My guess is that your zip file is broken.

Seems you are right. I extracted the zip contents using WinRar, recreated a new zip and Archive::Zips handles it fine. The funny thing is, that our software created the zip using the same version of Archive::Zip on it's own, before it extracted it using Archive::Zip again. Seems we are doing something wrong while creating the zip, which doesn't affect extracting the files using other zip programs, but does produce trouble in Archive::Zip when extracting more than once.

Thanks!