Hi all,
got my Desire yesterday and had the same problems as above. I have been trying everything today but I have found a solution which I hope works for you all -
If you didn't import your contacts as google mail linked type, then you'll have to re-import. If you did, skip to step 4.
1) The easiest way is to firstly export all your contacts to the SD card people>menu>import/export>export to sd card.
2) Next delete all the contacts on the phone
people>menu>delete>menu>select all>delete
3) Next reimport all the contacts from the SD card
people>menu>import/export>import from sd card.
It will give you the option to save as a google contact and this is the one you want.
4) Sync your phone to google. Go to home>menu>settings>accounts and sync>google account>sync now
5) If you have synced you contacts correctly to google mail contacts then you need to log in there and move all your contacts into the 'My Contacts' section. Just highlight all your contacts and select 'move to my contacts'. It doesn't change any group structures, I think it's just for syncing purposes.
6) Do another sync on your phone to google.
Once that's done give it a try!