This posting is older than 6 months and can contain outdated information.
Bluetooth is like Wireless LAN. If you reboot your computer, the WLAN 
connection will be terminated and needs to be reestablished. It's the 
same with Bluetooth.
At disconnect, the BD Remote enters a powersaving state, from which it 
needs to be woken by any button press. Once woken, it will 
automatically try to reconnect to Remote Buddy. That can take a few 
seconds.
For the BD Remote, you don't need to press the "pairing" button 
combination if you have paired your remote just with your Mac. Any 
button will be sufficient.
The prompt still asks for pressing both buttons, though, to cover rare 
edge cases. If a single button press doesn't lead to automatic pairing 
and you do have to press the pairing button combination, you should 
not press the two buttons several times (that'll reset the connection 
over and over again and give you the "disconnected" popup you 
describe), but rather keep them pressed for about 3-4 seconds.
Best regards, 
Felix Schwarz