Hi Android friends. First post from me. I had exactly the same issue as the OP and the fix suggested doesn't actually solve this problem. The issue is that syncing your contacts with googlemail won't sync the contacts saved to your phone. I have the answer!
Firstly go to people,menu,import/export and in turn export SIM,phone and Google contacts to SD card. Then still in people, menu, delete and delete all of your contacts (this will delete them from the phone but not the SD card). Then all you have to do is import the contacts from your SD card and select your google account as the destination.
Now you can go to accounts and sync, sync your contacts and the whole shebang should sync across with no problems.