Turn contact syncing off
Try browsing to /var/mobile/Library/addressbook
Delete whatever is inside (this WILL remove all your current contacts). Make a backup just in case
Respring, open contacts app and it should be empty now
Enable contact syncing in iCloud. Merge contacts. Make a new contact and see if syncs to iCloud now