I have Nuvi 360 and BB8310. Had the same issues with Bluetooth. Here is what I did and made it work.
1. Make sure you update Nuvi to latest Bluetooth firmware. You can get webupdater from Garmin. We'll Take You There.xxx8482;
and that would update firmware for you.
2. Go to Bluetooth Options and select Nuvi. Press the menu key and select options. Change "Address Book Transfer" to "All Entries". Save and Exit.
That worked for me. Hope it helps.