Open Regedit and navigate to:
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Policies\ActiveDesktop
-and-
HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\Policies\ActiveDesktop
Delete the value named "NoChangingWallpaper" (if present)
Navigate to:
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Policies\System
HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\Policies\System
Delete the values "Wallpaper" and "WallPaperStyle" in the right-pane.
Close Regedit.exe

Signature
Regards,
Ramesh Srinivasan, Microsoft MVP [Windows XP Shell/User]
Windows® XP Troubleshooting http://www.winhelponline.com
Sorry, that should be *(logged on as administrator)