I moved to a new host, and transferred my zenphoto along, too. I did a new 'setup' and the database reads fine, and the galleries show up to. However, the image caching is acting strange. I cannot see any cached images, but the images are being cached (they appear in subdirs of zenphoto/cache). However, they have 640 permissions. When I make them 777 permissions, I am able to see them in normal zenphoto.

Is this a setting I need changed in zenphoto? Or is there something strange/weird going on at my new hosting provider? An incorrect umask, perhaps?

What did Zenphoto's setup say about the permissions? Ideally they should be 0644 files/0755.
http://www.zenphoto.org/news/permissions-for-zenphoto-files-and-folders

You probably chose "strict+" for your file/folder permissions and that apparently does not work on your server for browser access. Change to simply "strict" via setup.