Lion allows you to set a different desktop picture in each space.
All you need to do is open System Preferences in the first space whose desktop you want to change, open Desktop & Screen Saver, and select a picture.
Then enter Mission Control, drag System Preferences to another space, and go to it. Change the desktop picture here, and you'll find it only affects the current space. And these changes are maintained between restarts, even if you choose not to 'Reopen windows when logging back in.'
Simple and somewhat intuitive, yes, but not necessarily obvious.
[crarko adds: That's actually pretty slick, and useful.]
Mac OS X Hints