NO thequark, eso es absolutamente anormal.
Rarísimo lo que comentas. ¿Esto te ha comenzado a suceder ahora? Si antes lo has hecho bien y ahora no, hay que buscar el problema en algún tocorreo o instalación sospechosa.
Si has conseguido cambiarlo con normalidad alguna vez, comenta que has hecho desde ese momento. Si no ha sido posible cambiarlo desde que tienes tu HD...
...Haz un Hard-reset y vuelve a intentar cambiar el fondo. Imagino que has hecho Soft-reset suficientes como para preguntarte.
Saludos