Thanks for all of the replies. I don't want to try the development nightly just yet, I'll try that as a last resort since I have close to 10k photos on the server right now.
I took a look through my apache's error log, and it looks like the .zip files are showing up as "not found". So I looked into each album's folder and sure enough, the ".zip" file was never created in the first place.
I finally realized that I was using symlinks for my albums, and zenphoto didn't have permissions to create .zip archives in the folders where the pictures are actually stored. DOH. So there, that was my issue. Thanks again for the help!