Weird it is. Oh, well that's just part of the fun thats Windows
Seems the easy tricks ain't helping. Apparently, you've got a permissions issue going on there, but what it is and why it might be I dunno.
Can you select a wallpaper from the default list?
What happens if you boot into safemode - is your wallpaper displayed then?
I'd like you try going to "My Pictures" or wherevever else you have image files. Select one you think would be a suitable wallpaper (big enough), right-click on it, select "Open with ... ", select "Internet Explorer", then, when it has opened, right-click in the image, select "Set as background", and lemme know what happens.
Can you post a HiJackThis log for me to look at?