A slight variation to Ryan's answer above is to load regedit and to navigate to the same key:
HKEY_CURRENT_USER\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies
Under this key there may be a key:
HKEY_CURRENT_USER\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\ActiveDesktop
If there is a string called "NoChangingWallPaper" set it to = "0"
Under the key:
HKEY_CURRENT_USER\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\System
If there are strings "Wallpaper" and "WallpaperStyle" then delete these two strings.
Close regedit and then go into the "Personalize" settings and you should be able to change the wallpaper to one of your choosing.
If this still doesn't work you may need to log out of Windows and log back in.
The above was tested successfully on Windows 10.
I also find that the Group Policy synchronisation is usually less frequent than daily (but I guess each environment could differ here). Logging onto your PC before connecting to the network can help reduce the frequency of the Group Policy re-sync as well. If you have a laptop and it supports hibernation this can also decrease the frequency of Group Policy re-sync. I can usually go at least a couple of weeks to a month without the group policy wallpaper being re-applied and this is without implementing any automation scripts on startup.
7They call it "policy" for a reason. Even if you knew what registry value to change, the policy would be reapplied the next time your computer processed policy. – William Jackson – 2011-05-23T13:18:25.983
2Any changes you make to your local GPO will be over riden by the domain GPO. – Joe Taylor – 2011-05-23T13:18:30.960
That said, do you know the location of the file that is used for the desktop background? Can you take the wallpaper you want and save it in that location? – William Jackson – 2011-05-23T13:19:29.883
As @William said, its there for a reason. Even if you do mange to get into the reg and change the key, policies tend to update every half hour or so, so this will just revert it back – beakersoft – 2011-05-23T13:24:26.247