The T-Mobile support person had me reset all the connections on my phone which removed the watch pairing and every other connection. I tried the "move watch to new phone" and it just fails with a "can not complete" message.
In the Wear app under managing devices, make sure that the watch is deleted from the old phone. Last evening I set up a GW4 for my wife on my phone, and used the Wear app to remove the watch from my phone first. When I attempted to add it to my wife's phone I was prompted to reset the watch. After that every thing went smoothly.
The watch was removed from the wear app - I even tried clearing app data and deleting the wear app altogether.
TThewatch was able to be added after a full reset, but one of the new features for the update is to be able to move the watch to a new phone without a full reset of the watch.
