I am having some incredibly frusterating sync problems with Lion and my iPhone. The problems started suddenly. Basically syncing goes through the routine but when it's all done the Address Book hasn't synced propertly.
I had a similar problem. It started after I synced several times between my mac (running OS X Lion), my iPad II, and some other devices. I found this articel of Apple's website that did the job: http://support.apple.com/kb/TS2481