First off, YES iPhone 4S DOES try to (and successfully does) sync up even when not connected to power cable, regardless of what the instructions say. Just like with PhotoStream and iCloud, when my iPhone is connected to wi-fi, it tries to connect to my PC, regardless of being plugged in or not. That's a FEATURE, in my mind. One that I assume they will "fix" when they patch it.
2ndly, I am experienceing mostly the same issues with this error. (Win 7, 64bit, ios5, icloud, iPhone 4S, newest iTunes)
The problem is intermittent. Sometimes happens when phone is plugged into charging cable, sometimes when it's not. Error message indicates no sync, but when I click "okay" the sync eventually initiates again and often works fine. It's irritating, but not debilitating. I'll roll with it until the patch fix.