We have Windows 7 Home Premium 3-bit on one computer and suddenly couldn’t change the wallpaper. This seems to be a problem out there. There can be various ways to fix it. This one worked for us:

1. Hit the Start ball
2. Type “adjust appearance”
3. A link called “Adjust the appearance and performance of Windows” will appear. Click that.
4. Toggle the top check box “Animate controls and elements inside windows”

Worked for us. Your actual mileage may vary.