iCloud Sync Borked on iPhone
Open Settings on your iPhone and find the iCloud settings page.

Find Contacts in the list, and switch it on.

If your contacts are still in iCloud, they will sync back to your iPhone.



Also check in System Preferences/iCloud on your Mac, and make sure those settings are correct, with contacts turned on.



Check your settings in iTunes, paying close attention to anything regarding "Contacts" under iTunes info tab

In the summary tab, you should have set things to sync to iCloud

Your info Contact settings should look like this: