Vamos a ver, ya se lo que te pasa, puesto que yo quité la galería de samsung, y le puse la original de google.
El problema es que al seleccionar un fondo de pantalla, antes de eso, sale un menú en la pantalla, para seleccionar la galería de donde quieres buscarla, y esa galería es la original de samsung. Si la quitas, no permite entrar a ese menú galería, y luego ya buscar en la galería que quieras.
No se si me he explicado, lo único que lo soluciona, es volver a poner la galería de Samsung, y luego no usarla, yo la tengo oculta en el launcher, y solo uso la de ICS original.