Acho que encontrei o problema: mesmo que eu vá até o arquivo, clique com o botão direito e diga "Definir como papel de parede ...", nada acontece. Então eu postulei que é o fato de o nome do arquivo não estar mudando a cada vez; O Linux tem algum tipo de economia de custo que eu não estou realmente atualizando, porque é o mesmo recurso de imagem. Para forçar o sistema a reconhecer que é uma nova imagem a cada vez, varie o nome do arquivo assim:
#!/bin/bash
# clear cache
PICS="/home/pvlkmrv/Pictures"
RAND=$RANDOM
rm -f ${PICS}/*.jpg
rm -f ${PICS}/photo-of-the-day
# download photo-of-the-day page
wget http://photography.nationalgeographic.com/photography/photo-of-the-day -O ${PICS}/photo-of-the-day
# parse the url out from the file
url='cat ${PICS}/photo-of-the-day | grep 'images.nationalgeographic.com.*cache.*990x742.jpg' | cut -d '"' -f 2'
# download the photo
wget http:$url -O ${PICS}/wall${RAND}.jpg
# set the desktop background
URI="file://${PICS}/wall${RAND}.jpg"
echo ${URI}
gsettings set org.gnome.desktop.background picture-options 'centered'
gsettings set org.gnome.desktop.background picture-uri "${URI}"