Try turning off Change Picture Every 5 minutes, give it some time them turning it back on again.
None of the 3 Macs I've tested have this problem. (but they don't match your Mac or OS version either)
The other thing your could try is going to User/Library/Preferences and Trashing
com.apple.systempreferences.plist and com.apple.desktop.plist
To Access you Library Folder in Finder hold down Option key and select Library from the Go menu