I discovered that the PathFinder application is the cause. Under its application menu there's a Show/Hide PathFinder Desktop item. I hid the PathFinder desktop and problem solved. It seems that the PathFinder desktop doesn't properly reflect the System Preferences. While it shows the first picture in the selected folder so it looks like your changes have taken effect, it seems to ignore the "Change Picture" checkbox.
I think this must have broken in a recent update as it used to work, which is why I didn't flag the presence of PathFinder above. I guess I should have anyway. Apologies for that.
Thanks for all help and suggestions.