It won't work for a while after changing time zones, IME. Even if you've done all the usual troubleshooting.
- Ensuring EPS is Current (including after updating via Wi-Fi connection).
- Ensuring using Galileo/Glonass.
- Ensuring recording every second.
- Synced with mobile and desktop apps.
- Ensuring watch software up-to-date including installing timezone update.
- Restarting watch.
- Standing in clear view of sky for 5-10 minutes (where it has connected previously without delay).
If anyone figures out the issue, please let me know.