Imported from the Apple Support Forums via the Wayback Machine 🔗
Instead of rebooting, use the Watch app on your iPhone to unpair it. That will back it up to the iPhone, then once it is unpaired then pair it again and select the most recent backup. If you continue to have trouble, repeat the process but don't load your Watch backup -- it could be corrupted in some way.
Note that watchOS 5.1.3 was just released yesterday (minor patches, no details which might explain your issue).