Two things:
First, it is not the file size of the image that matters, it is the dimensions. Zenphoto has to have enough memory to hold the expanded image and work on it. The trouble shooting guide has some examples of typical image dimensions and the memory required to hold the image.
Second, since these are (presumably) a lot of new images it may just be that the time needed to process the set on your server is too large. If this is the issue, the problem should resolve itself after a few timeouts when all (or most) of the images have been processed initially.
Third, there may be errors in the EXIF of some images that are causing the EXIF processing to loop. There have been some changes made in the nightly builds to try to detect this situation, so upgrading to the nightly build may help. Also running PHP version 5x may help as with version 5x we can trap errors in processing EXIF.