I was pushing a restrictions profile to my users that limited access in System Prefs. It also set the desktop background to /Library/Desktop Pictures/El Capitan 2.jpg. Even though I didn't click the checkbox for "lock desktop picture", my users were not able to change the image.
So, I removed the setting to set the desktop picture to /Library/Desktop Pictures/El Capitan 2.jpg, and re-pushed the profile. My users still cannot change their desktop background.
