I get the same error, and all my directories are chmoded to 777. Running the latest version of Zenphoto!
Edit:
It seems to be a bug in zenphoto. After I edited my album folder in zp-config.php to the default (/albums/) , and renamed my album folder back to 'albums' it works great.
see:
$conf['album_folder'] = '/albums/';