Sync problems are often messy things to untangle. Sometimes the best way is to start again. To do this, back-up your contacts, then wipe all the contacts on your phone:
Menu > Settings > Applications > Manage applications > All > Contacts Storage > Clear data.
Menu > Settings > Accounts & sync > Google > Remove account. Then, Power off phone > Remove battery for 30 seconnds > Replace and power on.
Set up your Google account on your phone again.
You could also try importing your contacts to your web-based Google contacts and syncing them to your phone (for the initial sync only), rather than from your phone to the web.
The other thing to look at is to make sure your web-based Google account settings are correct, e.g. using IMAP (which your phone should be using, too).