I actually just bought a Band on Sunday and paired it to my 830. I was having connection issues as well, where the pairing would repeatedly light up and disappear in the Bluetooth menu. Bear in mind, my 830 is paired to my home Wi-Fi, work Wi-Fi, Subaru BRZ Bluetooth system, Fitbit Flex, Nokia DT-903 (the new charging plate), and now my Band. Not sure if the giant list had anything to do with it, but I went ahead and removed the Flex and the DT-903 because I thought them "competing" for a connection might be a reason. Turns out, everything has been more or less okay since then. I only had one instance today where my Band keyboard got stuck on "Connecting when trying to compose a text reply. A restart fixed that.
In short, is your 830 connected to other Bluetooth devices nearby? My experience may at least be something to keep in mind. Good luck!