Like you said, find the proper resolution (whether it be 800x600 or 1024x768 - or more).
Also try SAVING the picture, then opening it, then setting it as your wallpaper.
If that still doesn't work, right click on your desktop, go to properties, go to desktop and play with the "Position" setting.