For me, this is what worked:
I noticed the last contact I added was in the Address Book, but all others were gone or missing.
I went to MS Outlook and ran the Sync program. Unchecked all options. Restarted the computer. Made sure the iCloud stuff was turned off on the phone and restarted it too for good measure.
When the macbook came back up when into outlook then MS Sync and turned contacts back on. Then connected the iphone and told it to replace all contacts. It worked.
Good luck. There is no one solution that seems to work for everyone, but testing different settings will hopefully get you to the point where your contacts go back onto the phone.
Cheers