Comment 8 for bug 625357

This caught me on upgrading from oneiric to precise, so it is still a problem.
I would suggest that the remove script (or a separate tool?) searches known methods for setting the wall paper (unity-2d, unity-3d, gnome2, gnome3, xfce, etc) for all users and deletes what is left. Otherwise every wallpaper-setting tool would need to be modified.