Bluetooth Authentication Error with Wacom Intuos 4 Wireless (Win 7x64)

Question

SITUATION
So my wife bought a Wacom 4 wireless tablet, and was using it with absolutely no problems for days. Then, one day, it just stopped working. I dug into it, and somehow her bluetooth services had been disabled. I restarted them, and was able to see the device. However, when I tried to connect it, I got the error in the screenshot attached to this. Note that when plugged into USB, it works fine. This is a situation similar to another issue, https://superuser.com/questions/304049/wacom-intuos4-wireless-doesnt-connect-to-bluetooth-or-visaversa, but it shows up and says it's connecting until it gives the error attached, and thus my issue is different.

EFFORTS
I've already gone to the Windows site and downloaded the troubleshooter, re-installed the bluetooth driver, re-installed the Wacom drivers. I've spent the last three days on google digging through every forum I can find. I've called Wacom and got snide remarks about making sure I had restarted the computer and not just closed the laptop lid (which, as an IT Professional I found incredibly unprofessional). I tested another bluetooth device on this computer, then another (My HTC Vision phone, and a Jabra BT8010). I also happen to have the exact same bluetooth card in my laptop that my wife has, so I went ahead and paired it with computer, and it worked just fine. At no point can I provide a pairing code on either the tablet or the laptop. I did have to when I paired with my cell phone, but it worked fine when I did.

THEORIES
+ Somehow the authentication pair has become corrupted for this device, and I need to find and delete it. But I have no clue where it is or how to do that.
+ There is some other service that handles authentication of devices without pairing pin codes, and I need to find it an enable it.
+ I have caused a tear in the fabric of space/time and created a condition that makes absolutely no sense from a diagnostic standpoint.

Answer 1

I had a very similar problem, and most of the steps I used to solve it were derived from NateDSaint's solution, with a few differences. I thought I should post my related answer here just in case someone comes across this excellent answer and may need a variation thereof.

As I just said, most of my problem was identical to NateDSaint's, with the exception that he seems to be running Windows 7 or earlier, while I'm running Windows 8.1, and I'm using an external Bluetooth adapter. These differences are significant, because uninstalling the Bluetooth stack will not remove the device driver for PTK-540WL (the Bluetooth driver associated with Wacom Intuos4), and the problem will not be resolved until all associated Wacom drivers are removed. So, here are the steps I followed to adjust my particular situation to NateDSaint's excellent solution:

1. Uninstall the Bluetooth driver stack from Programs and Features via the desktop (traditional) UI. Restart if prompted.
2. From the desktop UI, go to Control Panel >> Devices and Printers, and right click on PTK-540WL and select Remove.
3. For good measure, repeat step 2 for all devices associated with your Bluetooth adapter (headphones, keyboards, etc.)
4. Repeat step 2 for the Bluetooth adapter itself, then unplug the adapter.
5. Restart
6. Uninstall the Wacom Tablet driver from Programs and Features.
7. Restart
8. Plug in the Bluetooth adapter and wait for it to appear in Devices and Printers (desktop UI).
9. Right-click on the Bluetooth adapter's icon and select settings, then check the box to make your computer "discoverable"
10. Turn on the Wacom tablet without the USB cord plugged in, then chose "Add a device" from the Devices and Printers window.
11. Wait for the device name to show up (again, PTK-540WL), then select it and click "Install"
12. Once the device has been added, unplug the Bluetooth adapter
13. Restart
14. Re-install Wacom drivers
15. Plug the Bluetooth adapter back in
16. Make sure that the Bluetooth adapter is not set to "discoverable" in settings.
17. Turn on the Wacom tablet.

This should fix the problem for anyone with a setup similar to my own. I think my problem first occurred when I switched Bluetooth adapters, but didn't do a proper uninstall of the previous adapter before installing the new one, creating driver confusion. (I had both a Broadcom and Widcomm driver installed.) Sorry for all of the redundancy between my answer and Nate's, but I wanted to make sure people avoid all of the pitfalls I encountered, which caused me to waste about two hours too many on this issue (before discovering this thread).

Another tip or two: DO NOT use Device Manager to remove or uninstall Bluetooth devices. I tried this several times with no success, much to my frustration. Always remove the devices from Control Panel >> Devices and Printers, and just to be safe, always use the desktop UI instead of the Metro UI.

Answer 2

So there are still issues with the device, although we're still not sure if it's her computer, but the resolution for this was as follows:

Uninstall the Bluetooth stack (for this model of computer, it was the Dell Bluetooth Wireless 370 card using the WIDCOMM software suite.

Uninstall all traces of the Wacom drivers, including the wintab API.

Restart.

Re-install bluetooth drivers.

Restart.

In bluetooth options, make the computer "discoverable"

Turn on the bluetooth device, make sure it's in "pairing" mode (blinking blue light)

Go to add devices in bluetooth dialog in win7.

Wait for the generic mouse driver to show up, then disappear, then wait for the PTK-540WL to show up. Select the device.

Wait for automatic driver installation.

Reinstall wacom drivers.

Restart.

Before re-pairing, make the computer no longer "discoverable."

Pair the devices.

Go.

The problem that we're having now is that it'll randomly stop communicating and start back, up, which I've heard of a lot of bluetooth devices but this one doesn't do it any more often. If someone else has a more complete or definitive answer I'd be happy to choose theirs and give them the bounty.