[Helmling]

I changed all our iCloud passwords after Heartbleed (to be consistent with all our other new passwords) and somehow now my wife's 4S has no contacts. I've synced to its home computer, but they're still not on the phone. I turned contacts on and off under iCloud, nothing. I deleted the iCloud account from the phone and turned it back on, contacts and calendar are still gone. Now, Find My iPhone sees it just fine and photo stream appears to work just fine.

What the flip is happening and what can I do?

[ghporter]

In this order:
Turn OFF iCloud for your wife's phone.
Turn OFF iCloud for your wife's computer.
Sync the phone to her computer (which should restore contacts - verify this before proceding).
Turn ON iCloud for the computer.
Turn ON iCloud on your wife's phone.

At this point, you should have both the phone and iCloud synced with the same phonebook and calander entries. Verify this on the computer as well as the phone.