I have received about 50 emails thanking me for this fix posted on MSDN - so I thought I would post it here - and since I knew the answer figured minimum points would be acceptable to the membership.
I found that the Bluetooth Support Service must have the Log On tab as Local System account (you must stop/start the service after making change). After I did this I was able to add the bluetooth keyboard (which I'm using to type this) and Windows "found" the device and installed it.
So, just for those who have had a hard time finding the answer I have also added the following tags:
"Bluetooth Service Error"
"Access Denied"