Interesting not able to replicate it. Got it ONCE on one site but that would seem to suggest the cache was not updated and then since it did not appear again it updated
A community photo gallery - My Photo Gallery A community photo gallery - Omegatron Gallery A community photo gallery - ReefTalk Gallery
Every last one of those sites the cache is ON.
Try this turn off your cache but set the cache timeout to 10 or 15mins. Then view your index page of the gallery view a photo etc. Then try going back to your admin and turn on the category cache. What happens for you then?