"Issue occurred while checking for updates." new Teams cannot update...

ardamis UPDATE from our end:

Finally found in our environment what was causing the failure to update, or even launch after a day or two after a clean install.

Short story: we had a setting in one of our GPO's that set security permissions for the "C:\Program Files" directory. Part of that setting was set to "Replace" existing settings, instead of the "Propagate" option. Which means that any system added permissions will be wiped out during the next GPUpdate cycle.

What to look for: 

Immediately after installing New Teams, and while it is working normally, check the properties of the App directory. Located at "C:\Program Files\WindowsApps\MSTeams_24004.1309.2689.2246_x64__8wekyb3d8bbwe". Your version may be different, but the path should be the same. Go to the Security tab, and look for the APP Service account: "S-1-15-3-1327587233-2730283621-3908338074-337181141-3891108920-2047653661-4124462636". 

That is unique to the MSTeams App, and should be identical across all workstations.

If New Teams quits working, and that account is missing from the security tab, you have something in your environment setting directory permissions to one of the higher level directories. In our case it was a GPO Replacing permissions to the "C:\Program Files" directory. We changed the rule to "Propagate". Now, New Teams, and all other Apps installed within that directory, are working as designed. 

Seriously, I hope this helps. It was one of the longer investigations I have had to do in a while.

Best of luck.