The Fitbit Community is a gathering place for real people who wish to exchange ideas, solutions, tips, techniques, and insight about the Fitbit products and services they love. By joining our Community, you agree to uphold these guidelines, so please take a moment to look them over.
Did you contact support? I am not sure but I would have tried the option to replace device in the app. If phone is iphone, you might try forget device under bluetooth.