Activity GPS issues after watchOS 7 and iOS 14 updates

This morning I upgraded my iPhone XS Max to iOS 14 and my S4 Watch to watchOS 7. I then went for a run, using the Outdoor Run activity on my Watch as usual, holding my iPhone while I ran (as I was listening to a podcast with AirPods). When I finished, everything was recorded as normal, and I could sync the activity to Strava.

Later, I went for a walk. I used the Outdoor Walk activity on my Watch, but this time didn't take my iPhone. When I returned, and attempted to upload the activity to Strava, I received a warning that no GPS/route data was present. I checked the Fitness and Health apps, and sure enough, there was no route on the map - only the starting point.

I spoke to someone at Apple Support and they suggested I turned off/back on a couple of related privacy settings. I have since tried another Outdoor Walk activity, without the phone present, and the problem persists - no GPS/route data.

My wife also tried the same this evening, after upgrading her iPhone X and S4 Watch too. She had the same results - i.e. with just the Watch, no GPS/route information was saved with the activity.

This seems like a bug to me. Has anyone else experienced the same issue, or has any suggestions as to how to fix it?

[Re-Titled by Moderator]