Similar to #1094744, the Logitech Ultra Touch Mouse fails to reconnect after powering off or switching channels (this mouse can be associated with two devices). Adding a line to the PIN code database (/usr/share/gnome-bluetooth/pin-code-database.xml, see attachment) and then removing and re-adding the device resolves the problem for me.
For completeness, the specific device model is t630 (for Windows), for which all other functionality (including all gestures and battery information) seems to be working quite well. Some gestures result in key combinations that have no default action bound to them. There is also a Mac version called t631. I am uncertain if the latter has the same pairing issue.
Ubuntu 13.04, gnome-bluetooth 3.6.1-0ubuntu3.1.