I was getting this same error when setting up a child's Apple Watch SE (right after signing in with their Apple ID credentials). Here's what I did to resolve the issue:
-
Double checked the login creds by signing into icloud (the were correct)
-
Backed out and re-tried 4x (each time I got the same error)
-
Tried on a different internet connection (same error)
-
I setup the watch for ME, the same user as the phone. This went through without the error. I then updated the watch to the latest WatchOS, reset it and went back through and set it up for my child. (THIS TIME IT WORKED)
So, not sure if it was because I had created the child account during the process, or if it was because the Apple Watch needed to be updated, or if it was due to some other fluke... but I thought I'd share my solution in case it helps someone else who is banging their head against the wall.