I've been having the same problem of my iPhone not automatically backing up to iCloud BUT after trying everything suggested (including deleting all my previous manual back ups incase of corruption, without any change) mine finally worked last night! The thing I did differently was re read the instructions on my phone, and noticed the '...plugged in, locked, and connected to Wi-Fi.' I had been letting my phone auto lock. So, this time I plugged it in, turned on the power source and then pressed the Wake/Sleep button on the top to lock my phone. This morning I checked and I've my first auto back up. I hope this works for some others too. Good luck!