Our business has seen this start to pop up as well, very frustrating issue. It comes with an error code too that doesn't tell any more than that it's an error. Thanks Microsoft! We've had some success using the RDP app from the Microsoft Store but that doesn't work as well or as smoothly as a saved shortcut with the standard RDP client.
Microsoft, please fix this, you have taken a program that needed no changes and now made it useless, hugely impacting our customers and employees.