Former Member is on the right track. Make sure that you remove the watch from your phone's Bluetooth menu and from the Garmin Connect mobile app, then be sure to hard reset the watch.
To perform a hard reset, press and hold the power button on your watch. Ignore the "Power Off" question and the assistance alert (if applicable) on your watch, just continue holding the power button pressed down until the screen goes blank. Once this occurs, you may release the button. Allow the watch to sit powered off for a few seconds, then you may power it back on by pressing and releasing the power button.
Then, go through the normal pairing process, but be sure to put your watch into Bluetooth Pairing Mode before you prompt the app to add your device.
