Hey abb1,
I had the same problem with my HTC Fuze. What eventually worked for me was to download and install the demo of Jetware bluetooth software (http://www.jetwaremobile.com/).
Once installed, run the program and choose the "Options" softkey and from that menu choose "Phone Settings" (these instructions may or may not be exactly correct, I'm going off of memory here).
From the "Phone Settings" menu choose the left softkey menu (don't recall what is was named) and choose something like "Send Contacts". First it will have you select which categories of contacts to send (if you ha