Although reconnecting the bluetooth USB dongle is a good workaround for Ubuntu, it is starting to get a tad annoying.
On the Ubuntu forums, it is apparently just since the Edgy release that this occurs. There is a workaround by removing the bluez packages – although the side effect is that you cannot add other bluetooth devices.
As it happens, I’m not a huge fan of bluetooth devices anyway, so I’ll give this a shot.