I had this problem too, and after digging around in the code and debugging elements, I realized that this is something to do with the metadata of the images in the gallery. (this was only happening to me whenever I changed something in the gallery like updating the thumbnails or something).
Try going to the gallery in Gallery->Manage Galleries and choosing “import metadata” for the galleries that aren’t working. That fixed it for me.