FYI - Here's where I found the solution (though it's not written as clearly as I'm about to do it):
- (this might not be necessary?) Open your Contacts app, click the menu button > More > Import/Export Contacts > Export to SD card. This creates a .VCF file in the root-folder
- again click the menu button > Display Options, and disable the view of all built-in Phone contacts. Only leave your Gmail account selected. Don't freak-out when the Contacts list goes blank :-)
- again click the menu button > More > Import/Export Contacts > Import from SD card > Import from VCF
At this point all the contacts should re-appear and now they'll be marked (the tiny icon to the right of each entry) as both 'G' and 'P' for Gmail and Phone. Login to your Gmail account, click on the drop-down next to the big MAIL link (in the top-left) and select Contacts. Everything on the phone should now be there!