After hours of struggling with this and spending countless hours reading through different forums online; I stumbled on the solution and it was quite simple and straightforward. Phone must be on wifi; using your mobile data does not count as an "internet connection" (for whatever reason) Phone and watch must be closely within range. In my case, anything aside the phone and watch being side-by-side was not effective. Watch MUST be on charger all through the process. It worked seamlessly once all these were met. Not sure if this applies globally, but in my case this was it! Hope this helps someone. Cheers