I realised today that the 3rd Gen iPod Touch that I used to install iOS4 was missing the wallpapers. I could set the wallpaper to a photo of my choice but none of the default Apple wallpapers were showing up under Settings -> Wallpaper.
It seems that this happens if you used the iOS 4 GM image released to developers a few weeks ahead of the actual public release. The fix is to force an update via iTunes. To do this you first need to download the correct version of the OS image for the device. TUAW has links to the relevant Apple URLs for this.
Then with your device connected Alt-click the Check for Update button in iTunes and choose the image you just downloaded. After iTunes has finished you should have all of the default wallpapers back.