Joe Ellett said:
On the watch:
Settings, Unpair with phone.
Do not set up the watch yet.
On the phone:
In Android Wear use the Disconnect... option.
In Android Wear, use Settings, Device settings and touch the watch name, Touch UNPAIR WATCH.
Settings, Bluetooth. If you still see the watch, touch Forget... the watch so it no longer appears in the list of paired devices.
Settings, Device, Apps, select Google Play Services, Storage, Clear cache and Clear data. Uninstall updates.
Settings, Device, Apps, select Google App, Storage, Clear cache and Clear data. Also Uninstall updates.
Settings, Device, Apps, select Android Wear, Storage, Clear cache and Clear data. Also Uninstall updates.
Play Store, Apps, My apps, touch the Update all button.
Let all updates complete. This may take several hours. The best thing to do is to put your phone on its charger overnight, with the phone having a steady WiFi Internet connection. Double check the next morning by going to My Apps again.
Reboot.
Now set up the watch as if you had just unboxed it. Do NOT try to pair the watch manually, let the AW setup process do it for you.
Let all updates complete. This may take an hour or so. If your watch is one or more major releases behind it may take several hours. The best thing to do is to put your watch on its charger next to your phone on its charger, with the phone having a steady WiFi Internet connection.
Reboot watch and phone.
I had to tweak these instructions slightly on my LG G5. Instead of uninstalling updates on Android Wear, I had to uninstall and re-install, since it did not come with my phone. I skipped the step to clear Google App, so that may be an unnecessary step. I also skipped rebooting my phone and watch as the last step, since it was already working by that point.
Also fair warning, uninstalling updates to Google Play Services caused some of my other Google apps (calendar, inbox, etc) to start crashing and throwing errors. To be expected but when I updated Google Play Services again it lost my chrome bookmarks somehow.