I misspoke about immediately. What I meant is that you don't do anything else before you sync. Contacts are a 2-way sync. If you change a contact on the iPhone, it syncs to the computer. If you change a contact in Address Book, it syncs to the iPhone.
So, change a contact's pic on the iPhone and see if the contact picture in Address Book changes. If it's not, IDKY that's occurring (unless you have the contacts checked off on Replace Information on this iPhone in Advanced under the Info tab....I'm sure you wouldn't do that though).