Came here to say what worked! After nearly throwing my phone and my watch out the window, I found a fix in the answers here and wanted to restate it just in case someone else got as mad as I did. Simply uninstalling the Apple Watch app and redownloading it from the App Store fixed the issue. I tried everything else I found on all the other forums and this was all I needed to do. Good luck!