Ya veo...creo que una vez me salió también a mí ese mensaje pero no recuerdo como lo solucioné.
Puedes probar a ir a Ajustes/Aplicaciones/Todas y "deshabilitar" (NO desinstalar) la Galería, después reinicias el móvil, vuelves a entrar al mismo sitio y le das a "habilitar" la Galería.
Recuerdo que esto lo hice una vez, pero ojo fíjate bien y no le des a desinstalar, sino, repito, a "deshabilitar".
Otra cosa no te sé decir, si dices que has reinstalado el software y observas que después de realizar la operación que te he descrito te sigue sin funcionar bien yo que tú lo llevaría al servicio técnico.
(He visto que otra gente se ha encontrado con el mismo problema)