Try deleting the contact sync app on the BB. go to Google and have the link sent directly to your BB as a text. I had to do that a couple times on my 9800 to get Calendar Sync to work. And make sure you get the right sync for your model. I had an earlier one that wasn't compatible with my 9800. the latest one works fine.
i don't use contact sync, but it would seem it would work like calendar sync. I really doubt that VZW tech support would have a clue, especially since they dumped Google for Bing.