Its a very old thread but it seems to be still active so i thought i would contribute since i spent multiple days trying to get my girlfriends series 3 apple watch to work. Nothing seemed to work until i switched to my Guest wifi network (2.4Ghz). It doesn't hurt to reset both the phone and the watch too but what finally made it work was changing wifi networks