nose si ay algunprograma, pero puedes usarcrontab para correr un script ke te cambiel wallpaper XD

conozco desktopnova y wally pero la verdad nunca los he usado asi q no se q tal andaran

en compiz hay una aplicacion que se llama wallpaper cuando instalas los extras plugins

se que es como taaarde para responder pero el post sigue sin solución o al menos se olvidaron de marcarlo como solucionado y eventualmete esto podría servirle a alguien, hace exactamente 15 minutos cambié mi adorado icewm por openbox y empecé a trastear, navegando encontré esto

dijo:

http://braianet.blogspot.com/2008/03/colocar-wallpapers-aleatorios-en.html

creo que cubre las necesidades de la consulta
¡¡¡ME FALTA PROBARLO!!! así que quien lo haga que sea bajo su propio riesgo