I suggest you try Variety Wallpaper Changer - it is a new application that I've been working on during the past 2-3 months and I think it is shaping as one of the best wallpaper changers for Linux. Response from users so far has been vastly positive.
With it you can build a big collection of great wallpapers in no time and change very easily between them.
Project page and source-code
Installation (installs in /opt):
Or simply grab the latest deb from here
sudo add-apt-repository ppa:peterlevi/ppa
sudo apt-get update
sudo apt-get install variety
It should fairly soon appear in Ubuntu Software Center as well, I'm waiting for the review process to finish.