I just discovered I also had this problem on iTunes 11.0.1.12 (win 7) after updating my 4S to 6.1 (with a little CyEnhancement) a few days ago.
The first clue to 6.1 having a part in this was that the wi-fi sync was still working perfectly on my iPad 1 with 5.1.1 (also CyEnhanced).
After updating the 4S to 6.1, I had noticed that it was refusing to establish any new Bluetooth pairings - but quickly realised that there was a very easy workaround to this: reboot phone in safe mode, establish the pairing, then restart phone normally - pairing works normally.
So I tried this approach as soon as I saw that the 4S also wasn't playing nice with iTunes and read some of these posts. I'm pleased to say: problem solved.
It kinda makes me think that the source of this glitch might be somewhere than Apple 😉.
good luck to all - I hope this helps.