I too was having this issue (and not realizing it) for the better part of the last month since the 1.3.5 update. Since my 700+ contacts were previously synced to the phone when the update occurred, my sync failures were just limited to changes and new contacts (both directions -- to and from my phone) so I only realized the isssue earlier this week when I looked up an address I knew I had updated on my Pre a few weeks ago, only to see the old address still in place in Google..
To fix this, as suggested above, I went into my Google contacts and fixed all contacts with a number or symbol in them. It seems that some people have fixed the issues by only changing entries that begin with a number, symbol, or single character (W Hotel was one which caused a problem for me). Anyway, I did all of them that fit the bill.... I changed all numbers in the contact name to their text equivalent, I changed all "&" to "and" and I removed all symbols except periods in Dr.... I removed all apostrophes and possessives "Arturo's restaurant" to "Arturos Restaurant". After I did all of this (at www.google.com/contacts), I went into Contacts, then Preferences and selected Sync Now. After 5 or 10 minutes, all changes were updated (including new entries on the Pre which had not previously synced back to Google Contacts).
I assume you might have tried this already since I'm not saying anything new that's not already in the last few pages of this thread, but you didn't explicitly say you've tried this so I figured it couldn't hurt to share my experience from earlier this week and what worked for me.