I've checked and rechecked our settings. Teams apps --> Permission policies
Microsoft apps = Allow all apps
Third-party apps = Allow all apps
Custom apps = Allow all apps
Org-wide app settings
-->Third-party apps = On
Despite these settings, I still cannot see the Trello app to add it to a channel.
Could it be that Trello isn't allowed on our G3 tenant?