It has also happened to me about a month ago. After that one of my friend suggested me to reset my address book. After resetting the address book, all has started working as good as before. You may get some help on resetting your address book in the following link-
http://support.apple.com/kb/HT1497
I have done that before and it often, but not always works.
The problem is - you have to be at your Mac to do it.
Often I will update, say address book or calendar on my macbook pro, and then leave, to say fly somewhere.
By the time I realize that my iphone has not been updated, I'm sitting on a runway somewhere.
A few solutions;
1. reset every time after I update - kind of defeats the purpose of "da cloud" - sort of like Tattoo "Look boss, da claoud, da cloud"
2. carry my macbook pro with me - then why do I need an iphone, my old nokia was ok
3. have an app on the iphone that allows me to run "back to my mac" - assuming that apple fixes all the problems with BTMM.
It's like the instructions - Shampoo, Rinse, Repeat
only it's Update, sync, reset again and again.
I started to have this problem with my MAC Address Book after I upgraded my iPhone OS to 3.1.2. Anybody have similar experiences? Does Tech Support have an email address?
I am having a similar problem (iphone 3.1.2 / macbook pro 10.6.1). I use mac address book for my contacts, have made several changes to contacts while working on my mac, but am unable to get the updates transfered to my iphone. I do not use mobleMe, just sync it every day before I shut down. This means that I do not have iSync (I sync via iTunes and cable). I have tried restoring from back up and resetting as a new phone. Nothing works so far.