For example, if you have Change Picture set to Every Day, on restart you won't see a picture from your chosen folder until up to 24 hours later. Meanwhile you're stuck with the default (IMHO, ugly!).
Solution? Go into the preferences pane, untick and retick the Random Order box, and your desktop is refreshed with a new random image. You can automate with a short applescript and add it to Accounts » Login Items:
tell application "System Events"
tell current desktop
set random order to false
set random order to true
end tell
end tell
This bug has persisted on several of my machines through 10.5.7.
[robg adds: I don't see this issue on my laptop, which is presently booting between two OSes regularly -- when restarting in 10.5.7, one of my random images comes up. However, if it's happening to you, this is a pretty simple workaround.]

