I think that there is something to this.. The problem is that I was using a "replacement watch" that Apple sent to me, ;likely it was refurbished (so I can't remove this watch which is paired to another user). If anyone that is getting this error is using a watch that they bought from a third-party, they may be out of luck.