Recently I have been experiencing problems with my zenphoto, despite it working fine some weeks before. I used zenphoto-1.4.3.4.tar.gz. It asked me to re-install, and re-run setup. I don't know why.

I unpacked tarball, and ran setup. It asked me to change permissions to 777 on albums, cache*, zp-data, zp-core (maybe others). I immediately I was concerned, but I had a backup, so continued anyway. I changed the perms to 777.

The setup finished, but the cache/* files are being created as user 'nobody' and group 'nobody', where they used to be created as my username (on my shared hosting provider's servers).

I've contacted their support - they say nothing on their end has changed.

[b]Could there be something I've done wrong? I don't want 777 permissions, but if I don't use them, "nobody" is not able to make cache/* files any longer ... How do I fix this? [/b]

That sounds like a server configuration issue. The files should be created to the user Zenphoto runs under actually. Some detailed information on that:
http://www.zenphoto.org/news/permissions-for-zenphoto-files-and-folders