Hola
A mi me pasó lo mismo, y es que te estás quedando sin memoria principal del telefono.
Trata de desinstalar o mover aplicaciones a la SD(si no tienes te recomiendo comprar una de 8+G

.
Te recomiendo, si tienes rooteado el s3, instales Directory Bind (Soy nuevo y no te puedo dar links pero busca y en XDA lo encuentras), con el puedes mover carpetas a la SD sin tener que manipular las aplicaciones (por ejemplo los juegos de Gameloft).
Haz esto y seguro que recuperas tu galería.