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?