New address book entries on iPhone does not sync to iCloud
In your Macintosh Address Book, go to Preferences/Accounts and make sure that iCloud is listed there and enabled.

After doing that go back into Address Book and Click on the red bookmark so you're looking at the front page. It should say "iCloud" at the top of the list of folder/groups you may have there. If it says "On My Mac" then see if you can choose "iCloud."

The design of switching between "on my mac" and "iCloud" is confusing for us "old" mobileme users and my guess is it will change in time.