I also think this is related to iCloud somehow. I didn't set up iCloud for anything but Find My Iphone. I looked on the Iphone's iCloud settings, and like kojokylea said, it told me my iCloud password was invalid. I added edited my password, but all I got back was one contact (myself).
I am trying to set my phone up now to:
1. Backup to my pc via iTunes (like it's always done), and
2. Sync (apps, music, etc) to iTunes (like it's always done), and
3. Sync (contacts, notes, etc) to iCloud
ITunes backup and synch both work fine, but the ICloud sync does not. I first tried to set up Contacts to sync to iCloud from within iTunes, but there was no option for iCloud. So I changed the iCloud setting from the phone. When I chose Contacts, it said it would merge my contacts with what was previously synched to the pc. I didn't want this, but there was no other option, so I said ok. It also made me sign up for an iCloud email address...
But nothing is synching. I went into iCloud and nothing is there. (just the one contact - myself). When I go into iTunes, it says that my phone is set up to synch contacts with iCloud. There are no longer options to choose anything else. It says to change the iCloud sync settings, I need do this on my phone. But I cannot find any place to change the sync settings. I found one button to click to synch, but it just initiated the normal pc synch (it was connected to my pc at the time). That's not what I want. I want to synch the contacts, notes, and stuff to iCloud.
What do I need to do to activate it?