This is the natural behavior of Zenphoto. I know that's no excuse, but it's true. The gallery is not based on the database, but on the Filesystem. However, the Latest Albums hack [i]uses the database[/i] to get its information, so if the album hasn't been 'seen' and given a database entry, then Latest Albums won't know it even exists.
This is desirable behavior -- searching the filesystem on every page load would be very slow, and matching it with the already existing entries in the database even slower. So it's only done when absolutely needed, or when requested.
To refresh the database, just click the [refresh] link next to the stats on the zp Admin front page. Or, as you've discovered, just visit the album.
Come to think of it, the bug is actually in the Latest Albums hack, for going around Zenphoto's own methods, which get the current albums. (One line-- `$gallery->getAlbums(0);` would do the trick). Bypassing Zenphoto means nothing new is refreshed. I'll see if we can fix that.