I had this error too, b/c when I got the Hero the guy at the Sprint store copied over my old phone's contacts into the new Hero. Somehow doing this and then trying to sync with my Gmail contacts won't work. I'll bet that you have 255 contacts in your Gmail "All contacts" list.
The only way I got it to work, and this is kind of a pain, was to follow these steps.
1. In Settings -> Data Syncronization -> Google, uncheck Contacts.
2. Open "People", go to the "Groups" Tab. Hit "Menu", then choose "Sync Groups". I chose to sync "My Contacts" rather than "All Contacts".
3. In Gmail on the computer, I went into each contact in My Contacts and made sure that all the info from my old phonebook was in there, e.g everyone's phone numbers.
4. In Gmail on the computer again I went to export and backed up "My Contacts" to a Google CSV file.
5. I deleted all the contacts out of my phone, and all of the contacts out of Gmail on the computer.
6. I rechecked the Contacts sync box from step one.
7. On the computer I imported the CSV file from step 4 back into Gmail.
8. Let the phone sync.
After doing all that, Gmail and my phone sync without that error. There might be an easier way to do this, but that's what worked for me.