Wirelessly posted (iPhone 4 (32GB): Mozilla/5.0 (iPhone; U; CPU iPhone OS 4_0 like Mac OS X; en-us) AppleWebKit/532.9 (KHTML, like Gecko) Version/4.0.5 Mobile/8A293 Safari/6531.22.7)
Funny, I added a contact to Address Book on my Mac yesterday and waited for it to sync to my iPhone 4 (MobileMe) but it never did. I finally rebooted the phone and voilà! The contact synced. You might give it a shot.