Link to Windows is developed by Microsoft. Both the Windows side and the Android side. It just happens to be bundled with Samsung phones, and you can't uninstall it. However, you can roll it back to the original factory version. I did just that.
I linked my phone again. And then got this :
So, it looks like the protocol is not stable and they require both sides to be the same version. SMH.
Seems like one would need to roll back the version of the app on the Windows side, too to get it working again.
I'm not sure how to do that. It's possible to uninstall Phone link on the Windows side, but I just don't know where to download the older revision.