Hi I have the same problem with 3 computers, (all Running fully updated Windows 10) and have tried all of the suggested "fixes" for the issue none of which worked.
I have finally found a workaround that works but not a fix as I'm not sure what the cause of the issue is.
This works for me disconnect from the internet (either turn off the wireless connection or unplug the cable depending on your set up) and the start start the Solitaire collection.
I found that the game then starts but an error message shows about No internet connection.
then either turn on your wireless connection or plug the cable back in to reconnect the internet, when the connection is remade the error message goes. the game can then be played but you'll find that the premium account is not signed in (if you're signed up for it) if you're not continue to play with the ad's as normal.
I did not have Mahjong downloaded as another workaround solution suggested, I clicked on the Mahjong game in the collection and downloaded that from Microsoft store then pinned that shortcut to my start menu and then used that and to start which works without disconnecting from the internet. although an error message comes up that the link is invalid when you select the solitaire collection it does in fact work and the premium account is signed into.
it looks as though that Microsoft did an update a few days ago and there is an error in the startup script for Xbox/Solitaire casual games.