Toggle contacts off in Settings > iCloud. Choose to keep the contacts locally on your iPhone when prompted.
After 5 minutes, toggle contacts back on in Settings > iCloud.
It should sync now. If it doesn't, please join our forum and let us know in *this* thread. Hopefully someone else can come up with another solution if that's the case.