Yay, glad we figured it out! Sorry it took me so long to figure out what was going on.
That privacy setting was added in iOS 10. When you first tried to access the iTunes library after the iOS 10 update, it should have presented you with one of those messages "Walkout Songs requires access to your Music Library". If you accidentally tapped no instead of yes, then that's how it got disabled.