Go to Start, type regedit and open the application. Navigate to HKEY-LOCAL-MACHINE > SOFTWARE > Microsoft > Windows > CurrentVersion > Policies and click the ActiveDesktop folder. Select the NoChangingWallPaper entry, double-click the DWORD value and change it to 0. Also, go to Start > Control Panel > Ease of Access > Ease of Access Center, select Make the computer easier to see and make sure that Remove background images box is not checked.
If the problem is not solved, go to Start, type Edit group policy and open the application. Navigate to User Configuration > Administrative Templates > Desktop > Desktop again and double-click the Desktop WallpaperSelect. Click Not Configured, Apply and then OK.
If you're using Windows 7, go to Start, type
%USERPROFILE%\AppData\Roaming\Microsoft\Windows\Themes\ and press the Enter key. Right-click the TranscodedWallpaper.jpg file select Rename and change its name to TranscodedWallpaper.old. If there is a slideshow.ini file, open it and remove all the text. Save the file and try to apply a background picture again.
If the problem is not solved, check the Microsoft Support page for further solutions.