I had the exact same problem. It was fixed in my case by making the album folders chmod 0775 and the files chmod 0664
The advice given previously by another user to do chmod -R 0755 is wrong as that will set all files within the folder and sub folders to 0755 as well as the folders which is not what you want.
On my ISP the web server is a member of the group and so when permissions are set for a folder as 0755, that is
owner group other
rwx r-x r-x
the web server is unable to write to the directory and so image updates fail.
As far as I know the instructions in the docs at http://www.zenphoto.org/news/permissions-for-zenphoto-files-and-folders are not correct, as they say " 0644 files/0755 directories ([rw-r--r--] files and [rwxr-xr-x] directories) permissions, with [youruser:webservergroup] ownership" on the one hand, but then follow that with "keep ownership of the files yourself, give group access to the web server, and shut everyone else out." Sadly the "0644 files/0755 directories" disallows by definition "group access to the web server" and so will not work except where the webserver is running as owner which would be very unusual. To do as is initially suggested will normally require 0664 files/0775 directories. I have just filed a bug about this doc issue.