Different wallpapers in Gnome
Write a little python daemon that uses the libwnck bindings in gnome-python-extras (see Ubuntu bug #6301 to get them fixed in Breezy) which switches the background to something else whenever you switch workspaces, thus making it look like there's a different background on each virtual desktop. Davyd Madeley has code to change the background from Python using gconf.