I had noticed that my iPad Air 1 and my iPhone 6 Plus weren't doing iCloud backups on there own either just yesterday as my phone and iPad notified me that no backups have occured for about a month. I have been enrolled in and running the new iOS 9 Public Beta. I just completed a backup on each this morning. The key difference that I noticed is that this time I kept the backup UI open once I started the backup and didn't navigate away from the page and--voila!--the backups completed just like clockwork. Normally, you can navigate away from the page while the backup runs in the background, but not right now, apparently. Maybe there is some sort of bug in existence right now that forces you to stay on the page while the backup completes. ? Try that.