I've verified that at least some of my contacts are not properly syncing between my iPhone running iOS 5.1 and my Mac running OSX 10.7.3 (both the latest OS versions currently available).
Here, you can see that the contact named "Android Standup" is available on my iPhone but not available on my Mac:
I have iCloud set up to sync Contacts on both devices, and both are using the same iCloud account:
The "Android Standup" contact is only available on the phone. It's not available on iCloud.com or on my mac.
However, I verified that contact sync IS WORKING for some contacts. I just created a new "Test Contact 1" on my phone, and it appeared almost immediately in my Mac's Address Book.
Why are some of my contacts (such as the Android Standup contact) not syncing to iCloud?