I have a dell Inspiron N5010 and I recently purchased a Byte Corseca BT Headset. I have the default Dell 365 Bluetooth adapter, Windows 7 home premium and Ubuntu 12.04

I added the BT headset to Windows first, and it worked fine. The next time I logged into ubuntu, I paired it there too. Everything was fine.
The next time I booted into windows, I tried to connect to device and was unsuccessful. After a half hour of poking around, I finally removed the device and added it again. It Worked.
Here's where things get really messed up: Now I faced the same problem in Ubuntu and had to resort to the same solution.

Right now, I have to remove and add every time I switch OSes. This takes 10 minutes every time.
Can anyone please help ??