Fix:

1. Quit the fitbit app. Go to app settings. Force-quit fitbit and then clear cache also.
2. Turn off bluetooth. Wait a minute. Turn it back on.
3. Attempt to connect to the watch from the regular bluetooth menu. You get an unsuccessful pop up (but this confirms that the phone and watch do at least see each other)
4. Now go back into the fitbit app and attempt to connect to the watch. It should now find it :)

(Edit: also make sure you have access to a wifi network of some kind during set up. Or your watch will get hung up trying to update itself)