Cannot get PC to recognize my bluetooth keyboard

[Hensley300]

Seems like a simple enough task. Im leaning toward a keyboard problem but just wanted more thoughts. It has worked before but ususally I would turn off my pc and when I would turn it back on the pc wouldnt find it. Now it wont find it at all.
Its a MS Keyboard Elite for bluetooth keyboard. Mouse works just fine. Ive changed batteries. Ive pressed the connect button close to the pc during the add procedure, nothing. Ive reinstalled software, nada. Still mouse works fine. Ive looked for updated drivers, they dont do the trick.
I did notice when I was uninstalling I wasnt able to get all of the bluetooth stuff of my pc as the bluetooth icon was still in the control panel. No bluetooth software was in the add/remove programs section though.
Anythoughts besides getting a new keyboard?