Мне удалось это решить.
Я забыл упомянуть, что мой компьютер - Lenovo S10e, у которого есть адаптер Broadcom Bluetooth.
Windows 7 продолжала предлагать обновить драйверы Bluetooth с веб-сайта Broadcom, но это не сработало - при установке не удалось найти мой адаптер.
Я наткнулся на тему на форумах Lenovo S10, где предлагалось установить драйвер Broadcom Bluetooth для Vista. Я скачал драйверы из этой ветки и перед установкой отключил драйверы Bluetooth по умолчанию на панели управления.
После установки я попытался снова подключить гарнитуру - не только она была распознана - я также получил диалоговое окно мастера, спрашивающее меня, хочу ли я использовать гарнитуру со Skype! Так что после примерно 2 кликов все заработало. Меня попросили разрешить BTStackServer в Skype, но это было все!