hi man, also had this problem today, luckily didn't take me that much to have it working.
read about 20-30 posts about albums, .htaccess and everything barely related... the install wrongly "self-detected" the path to /zp, NOT /zenphoto, so I had to do the .htaccess thing,
.htaccess detected zenphoto in /zp, so it had:
RewriteBase /zp
but I had zenphoto installed in /zenphoto, so just changed the text to:
RewriteBase /zenphoto
but yeah, it's a hell if it doesn't work.
P.S.: Do I have to jack-off?

see ya