La galeria stock tiene muchos fallos, yo también la utilizo aunque hay mejores alternativas, como Quickpic.
Sobre tu problema, tienes que forzar el escaneo de contenido multimedia para que se actualice la galería.
Supongo que debería hacerlo sólo al descargar imágenes (según el navegador que utilices), pero si no lo hace, en lugar de reiniciar el teléfono, puedes hacer cualquier operación de copiar/mover/borrar/renombrar un archivo con el gestor de serie, el "Mis Archivos", y eso iniciará la búsqueda.
Verás aparecer "Multimedia" en la lista de procesos en ejecución durante un minuto o dos.
Por ejemplo, si la tienes vacía, te cargas la carpeta "Video" en la raiz de la memoria interna, el teléfono la volverá a crear. O las carpetas "tmp" o "temp" vienen bien para estas cosas
