Have you tried deleting the Garmin from the Bluetooth List and re-pairing it?
Since you have deleted EVERYTHING do the following to downgrade:
1. Install Desktop Manager 4.2 SP1.
2. Install the OS you wish to downgrade to onto your PC.
3. Delete the Vendor.xml file
4. Plug in the BB, open Desktop Manager and run Application Loader.
5. It should see the old OS and ask if you want to downgrade.
Note: If you wish you can wipe with JL_Cmder and reload the OS after that. See
Main Page - BlackBerryFAQ for lots more info on this.