Crap.. I recall having such an issue, but can't remember how I solved it.. Can you try turning Bluetooth on (or toggle it). I recall there being some strange link behavior between the 2.
I had ignored it for the longest time since I was typically hardwired, but eventually I managed to get it going.