I was having the same problem with my Curve and Nuvi 680. What has fixed this for me is downgrading the Bluetooth firmware version on the Nuvi itself. I was running version 3.0 (you can check your version by going to Settings -> System -> About on the Nuvi) -- I had success after downgrading to version 2.4.
It's a bit of a convoluted process, but here is the procedure I followed:
1. Download the old Nuvi BT firmware from the Garmin Italy website:
2. Connect your Nuvi to your PC.
3. Go into the X:\Garmin\RemoteSW and look for a file called 006B055301.GCD (where X: is your Nuvi drive)
4. Back up that file to your computer, and delete it from the Nuvi.
5. Extract the file in the zip downloaded in step 1 to the X:\Garmin\RemoteSW directory
6. Disconnect your Nuvi from your computer, and let it reboot
7. Click on "View Map," then touch the "Speed" in the lower left corner.
8. You should have the "Dashboard" view up. Touch and hold the "Moving Average" box for ~15 seconds until the diagnostic screen appears.
9. Press the "next" button until you arrive at the "Bluetooth Status" screen (5-6 screens in)
10. Click "Updt PR" and then click "Yes"
11. Reboot the Nuvi, delete the existing bluetooth pairing, and attempt to re-pair with your BlackBerry.
Seems to work perfectly now -- please let me know if you have any questions. Good luck!