Works for me on Lumia 735 and Win10Mobile 10512, however I think I initially set the device to be associated with my fitbit account with the desktop fitbit connect app. Also, make sure you go into the Bluetooth settings and pair the Charge HR before trying to connect with the fitbit app.
In the end rolled back but again couldnt connect it. The i goun an article on how to delete all data from Fitbit. Did that and on the first try: Connection established!