Why aren't my contacts syncing?

I just got a shiny new iPhone 4! The problem is, I can't get my contacts synced... On the phone itself it says iCloud syncing of contacts is off; but if I try to turn it on, the whole settings app crashes. On iTunes if I tell it to sync contacts from my MacBook, it says it cannot do so because they are being synced over the air by iCloud! It's been doing this since I first tried to sync it, so I don't think I could have done anything to it digitally. What is wrong, and how can I fix this?

More info that may or may not be relevant:

iTunes version is 10.6 running on a MacBook Pro

iPhone is iOS 5.1 with a semitethered jailbreak

I have an iPad and a MacBook Pro using my iCloud account