Let me tell you what I just did.
Just got the phone tonight (it's still tonight, I haven't been to bed yet.) Don't have it activated yet.
My phone book from my last phone was backed up using Backup Assistant (free for Verizonwireless customers.)
I went to the Verizonwireless site, clicked on My Services, and Backup Assistant is the last choice in the drop down menu. Once on this page, look at the View options. If you choose the one with three lines, it makes a list of them. Then click on Select All, and click on the gear next to it for a drop down, and choose Export Contacts. I chose the .CSV (Outlook) format.
You can then go into your Gmail contacts, and import this .CSV file. When I did so, it imported 120 contacts, merging 16 of them automatically. The rest that I had duplicates on, I just checked all the entries for one person and merged them, checking to make sure an old number wasn't included in the merge. I got everything down to 106 contacts (weeded out some folks I didn't know/remember) then went to Account/Sync in Settings on the Incredible, and had it sync Contacts.
If you did the linking on the phone, have you run the sync? If not, that might be why it's not showing up. I'm assuming that the sync takes into account which device (pc or phone) has the most current data, as that would only make sense.
Anyway, I did all my syncing via WiFi, and downloaded some apps, too, all with no phone number associated, so no data used.