I shall not pretend to know what the problem is, but I can state what is supposed to happen. It has been a while since I used Gnome, but I remember, assuming you are using Squeeze with Gnome 2, that desktop settings has a section with available wallpapers. Any image selected as a backdrop is automatically added to the selection and stays there, until removed. When changing the backdrop, it is a matter of clicking on a different image.
That is how it is supposed to work. Why it is not?
For now, try Caravel's idea and see what happens.