Whith cheap web hosting, php memory is limited to 32MB.
Then, when loading a large-sized image, ZenPhoto fail to create thumbnail/cache.
In this failure case, my proposal is just to show the full original image as a thumbnail, instead of nothing. In other words, let the browser resize the image client-side.
This is a hack, but it should be easier to implement and to use than ImageMagic.

When the resizing fails, the error aborts the script, so there is not much we can do. PHP 5 might be able to trap the abort, but PHP 4 cannot.

Besides that letting the browser scale down big images is bad webdesign practice since forever... I would think the best fix is not to upload images bigger than your server can handle.