I can still sync w/ iCloud turned on....
When I had something similar happen, I resolved it by resetting the sync history.
If you are still having trouble, try re-setting the sync history for that device. Go to Edit, then Preferences, then Devices. Select your iPhone and select Reset Sync History.