You are actually on the right track!
For some reason, iCloud is automatically syncing/backing up, now. I edited a contact in my Contacts list, and when I checked iCloud online, it was already synced with the change that I had in my iPhone.
So, this is probably where the problem is. It used to be that iCloud would back up the information/documents/settings only when manually told to do so or when the "iPhone is plugged in, locked, and connected to Wi-Fi" - if that option is turned on, of course.
I believe that it's a glitch since Photo Stream was introduced. Because there is automatic syncing with iCloud and Photo Stream, somehow, that affected iCloud's automatic syncing/backup altogether.
This is a BAD thing, not only because it drains the battery faster since it's constantly running in the background, but because any ACCIDENTAL CHANGES on the phone are automatically backed up to iCloud.
I just deleted a contact to test this, and as soon I saw those "swirling sun rays" in the status bar, the change had been made to iCloud.
Therefore, if EVERYTHING is deleted from an iDevice running iOS 6, the same will happen to everything in iCloud, which defeats the purpose of retrieving anything through iCloud.
In other words, iDevices running iOS 6 are backing up to iCloud when not asked/scheduled to do so (even though "iCloud > Storage & Backup > [under] Back Up Now" says otherwise).
The only thing that it should automatically be syncing with is Find My iPhone/iPad/etc.