About a year ago I wrote about how to change the desktop wallpaper using SystemParametersInfo(SPI_SETDESKWALLPAPER).
Windows 8 desktop apps (not Store apps) can use the new IDesktopWallpaper API to get a more fine level of control. So I wrote an app which uses the new API, though I just set the background on all monitors to the same image path, and I don't exercise any of the advanced features of the API.
Setting the desktop wallpaper to C:\Users\MatEer\pictures\theda-bara.bmp succeeded.
Source and binaries attached
EDIT September 22 2015: moved source to github https://github.com/mvaneerde/blog/tree/master/desktopwallpaper