I suspect the problem may be where your phone contacts are stored. On Android phones, when you enter a new contact, you can make it a Google contact or a Phone contact. Google contacts will sync with your Gmail account, but Phone contacts will only stay local on your device, and will not sync with Gmail. You can tell what kind of contact it is by selecting Edit from the menu, and looking at the label on the top.
A quick web search didn't reveal any quick and easy way to convert your Phone contacts into Google contacts. If you don't have many contacts, it may be easiest just to re-enter them into your Google Contacts on a desktop browser, which will then sync with your phone. If you have a lot of Phone contacts, then you could try the following:
1. Using HTC Sync, sync your Phone contacts with Microsoft Outlook on your desktop or laptop. Download HTC Sync here:
2. From Microsoft Outlook, export your contacts to Google following these steps:
I hope this is what you were specifically asking about. Anyone else know of an easier way?