I had a whole bunch of wallpapers lying around, but they were all different sizes, which really looks screwy on a dual screen setup.

The attached perl script reads through all images in $HOME/Pictures.original/ and creates new copies in $HOME/Pictures/ as the specified image size in the file.

By setting the image size to exactly the size of one of the dual screen monitors (this assumes identical resolutions on both screens), and running the script, the backgrounds then work nicely.

I use http://www.autowallpaper.org/ on gnome to automatically rotate the wallpapers as well, despite it having a couple of bugs, it seems to work pretty well once going.