Ich hatte genau das gleiche Problem (mit einer Series 2 und einem iPhone 7).
Wie die Anderen habe ich auch diverse Varianten versucht. Apple Watch & iPhone neustarten. Das Update auf der Uhr herunterladen, dort ließ es sich dann aber nicht starten, dann am iPhone gestartet Und wieder der Fehler. Dann ließ es sich irgendwann doch auf der Uhr starten, und nach einigen Minuten wurde mir dann auf dem iPhone wieder die Fehlermeldung angezeigt.
Die oben beschrieben Probleme waren auch noch mit dem Softwareupdate auf 6.2.1 noch da. Also habe ich den Apple Support angerufen. Dieser hat eine Diagnose der Uhr gemacht und dabei festgestellt das alles bestens ist, sein Tipp war die Uhr noch ein Mal zu entkoppeln und neu zu Koppel und dann aus dem Backup wiederherzustellen. Gesagt getan, doch erneut die gleichen Probleme.
Am Ende funktioniert hat die Variante am iPhone WLAN und Bluetooth zu deaktivieren, auf der Apple Watch das Update zu laden und dann auf das Ladekabel zu legen. Prompt startete sich die Uhr neu und installierte das aktuellste Update.