Here is a workaround if you are the local admin on your machine:
...and if you can find the image that the policy is using to set your wallpaper (in my case it was in C:\Windows\Web\wallpaper\backround.jpeg) you can change it's security permissions to deny all.
Next time you log in, the policy will not be able to overwrite the image or set it as wallpaper and hence it will default to a solid colour background. In my case I am still not able to choose a new image for the background because group policy disabled that option; I am however able to choose the Windows 7 default theme which set the background to default black.
I only wanted a black background in my case so I did not try to tinker around with the various read/write/modify permissions on the image itself. However, theoretically, you may be able to make your own image, name it the same as the default group policy background image, replace the default image with the new, change permissions on all groups, users to read only. This way the policy should fail to overwrite the image but succeed to set it as the default background. I have not tried this last bit.
This is the only solution I know off that is not temporary. All other solutions, including those that change the registry settings, will be overwritten by the policy every time you log in.
I tried using DisplayFusion and it does work but the change is temporary to the current session; DisplayFusion software will change the wallpaper to any of your chosing but every time you log out and back in and policy is re-applied, you will have to open DisplayFusion and hit OK to update the wallpaper.