I had something similar but not the exact message. Apparently the iPhone could not connect to the watch even though everything looked OK. After some investigation, I put the watch into airplane mode and then back again. From what I've read, you nay have to do this a few times. {toggle Airplane Mode} It worked for me.
Apparently it resets the connections to the iPhone.. good luck.