OK, you kinda go back and forth here, so let's try to figure this out:
It sounds like the VZW store manually transferred your contacts into the Droid from the Samsung phone.
Once they did that, the contacts should go off and sync to the Gmail account attached to your phone, assuming they set it up that way. So, you have them on both the Droid and on Google.
I came in the other way. I set up Google Sync on the WinMo phone, had it grab the WinMo contacts and populate Gmail, then when I first set up the Droid with the same Gmail account, it grabbed the contacts there.
Either way, it should work.